@@ -0,0 +1,1839 @@
+package advanced.combinatorial.subset.lc494_targetsum;%0A%0Aimport java.util.LinkedList;%0Aimport java.util.Queue;%0A%0A/**%0A * You are given a list of non-negative integers, a1, a2, ..., an, and a target, S.%0A * Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.%0A * Find out how many ways to assign symbols to make sum of integers equal to target S.%0A */%0Apublic class Solution %7B%0A%0A    // TLE...%0A    public int findTargetSumWays(int%5B%5D nums, int S) %7B%0A        Queue%3CInteger%3E q = new LinkedList%3C%3E();%0A        q.offer(0);%0A        int cnt = 0, n = nums.length;%0A        for (int i = 0; i %3C n; i++) %7B%0A            for (int j = q.size(); j %3E 0; j--) %7B%0A                int sum = q.poll();%0A                q.offer(sum + nums%5Bi%5D);%0A                q.offer(sum - nums%5Bi%5D);%0A%0A                if (i == n - 1) %7B%0A                    if (sum + nums%5Bi%5D == S) cnt++;%0A                    if (sum - nums%5Bi%5D == S) cnt++;%0A                %7D%0A            %7D%0A        %7D%0A        return cnt;%0A    %7D%0A%0A    public int findTargetSumWays_queue(int%5B%5D nums, int S) %7B%0A        Queue%3CInteger%3E q = new LinkedList%3C%3E();%0A        q.offer(0);%0A        for (int num : nums) %7B%0A            for (int i = q.size(); i %3E 0; i--) %7B%0A                int sum = q.poll();%0A                q.offer(sum + num);%0A                q.offer(sum - num);%0A            %7D%0A        %7D%0A%0A        int cnt = 0;%0A        while (!q.isEmpty()) %7B%0A            if (q.poll() == S) cnt++;%0A        %7D%0A        return cnt;%0A    %7D%0A%0A    public int findTargetSumWays_dfs(int%5B%5D nums, int S) %7B%0A        return dfs(nums, 0, S, 0);%0A    %7D%0A%0A    private int dfs(int%5B%5D nums, int sum, int target, int k) %7B%0A        if (nums.length == k) %7B%0A            return sum == target ? 1 : 0;%0A        %7D%0A        return dfs(nums, sum + nums%5Bk%5D, target, k + 1) +%0A                dfs(nums, sum - nums%5Bk%5D, target, k + 1);%0A    %7D%0A%0A%7D%0A

target sum