Java Solution with HashMap


  • 0
    Y

    From the first number to the last, for each number we save all possible sum so far. For a given sum as the key, we save the combination count as the value.

        public int findTargetSumWays(int[] nums, int S) {
            HashMap<Integer, Integer> last = new HashMap<>();
            if (nums[0] == 0) {
                last.put(0, 2);
            } else {
                last.put(nums[0], 1);
                last.put(-nums[0], 1);
            }
            for (int i = 1; i < nums.length; i++) {
                HashMap<Integer, Integer> cur = new HashMap<>();
                for (Integer x : last.keySet()) {
                    if (nums[i] == 0) {
                        cur.put(x, (cur.getOrDefault(x, 0) + last.get(x)) * 2);
                    } else {
                        cur.put(x + nums[i], cur.getOrDefault(x + nums[i], 0) + last.get(x));
                        cur.put(x - nums[i], cur.getOrDefault(x - nums[i], 0) + last.get(x));
                    }
                }
                last = cur;
            }
    
            return last.getOrDefault(S, 0);
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.