@@ -0,0 +1,2451 @@
+package depth_first_search.all_subsets;%0A%0Apublic class TargetSum %7B%0A%0A    //TAG: Google%0A    //TAG: Facebook%0A    //TAG: dfs%0A    //TAG: dp%0A    //Difficulty: meidum%0A%0A    /**%0A     * 494. Target Sum%0A     * You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.%0A     *%0A     * Find out how many ways to assign symbols to make sum of integers equal to target S.%0A     *%0A     * Example 1:%0A     * Input: nums is %5B1, 1, 1, 1, 1%5D, S is 3.%0A     * Output: 5%0A     * Explanation:%0A     *%0A     * -1+1+1+1+1 = 3%0A     * +1-1+1+1+1 = 3%0A     * +1+1-1+1+1 = 3%0A     * +1+1+1-1+1 = 3%0A     * +1+1+1+1-1 = 3%0A     *%0A     * There are 5 ways to assign symbols to make the sum of nums be target 3.%0A     * Note:%0A     * The length of the given array is positive and will not exceed 20.%0A     * The sum of elements in the given array will not exceed 1000.%0A     * Your output answer is guaranteed to be fitted in a 32-bit integer.%0A     */%0A%0A    /*%0A    Solution:%0A    it's all subsets problem, which for each num there's two condition add to result which is num and -num%0A%0A    Time: O(2%5En)%0A    Space: O(n)%0A     */%0A%0A    int count = 0;%0A    public int findTargetSumWays(int%5B%5D nums, int S) %7B%0A        findTargetSumWaysHelper(nums, 0, 0, S);%0A        return count;%0A    %7D%0A%0A    private void findTargetSumWaysHelper(int%5B%5D nums, int cur, int index, int S) %7B%0A        if (index == nums.length) %7B%0A            if (cur == S) count++;%0A            return;%0A        %7D%0A        findTargetSumWaysHelper(nums, cur + nums%5Bindex%5D, index + 1, S);%0A        findTargetSumWaysHelper(nums, cur - nums%5Bindex%5D, index + 1, S);%0A    %7D%0A%0A    /*%0A    Solution 2:%0A    Many calculation is duplicated, e.g. 1 + 2 + 3 and -1 + 2 + 3, 2 + 3 part is duplicated%0A    So just record current pos sum is enough%0A    https://leetcode.com/problems/target-sum/discuss/97334/Java-(15-ms)-C++-(3-ms)-O(ns)-iterative-DP-solution-using-subset-sum-with-explanation%0A     */%0A%0A    public int findTargetSumWays2(int%5B%5D nums, int s) %7B%0A        int sum = 0;%0A        for (int n : nums)%0A            sum += n;%0A        return sum %3C s %7C%7C (s + sum) %25 2 %3E 0 ? 0 : subsetSum(nums, (s + sum) %3E%3E%3E 1);%0A    %7D%0A%0A    private int subsetSum(int%5B%5D nums, int s) %7B%0A        int%5B%5D dp = new int%5Bs + 1%5D;%0A        dp%5B0%5D = 1;%0A        for (int n : nums)%0A            for (int i = s; i %3E= n; i--)%0A                dp%5Bi%5D += dp%5Bi - n%5D;%0A        return dp%5Bs%5D;%0A    %7D%0A%0A%7D%0A

494. Target Sum