494. Target Sum

DFS (backtracking)

T: O(2^n)

S:O(n)

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int[] result = new int[1];
        backtracking(0, nums, target, result);
        return result[0];
    }
    private void backtracking(int start, int[] nums, int remain, int[] result) {
        if (start == nums.length) {
            if (remain == 0) {
                result[0]++;
            }
            return;
        }

        remain += nums[start];
        backtracking(start+1, nums, remain, result);
        remain -= nums[start];

        remain -= nums[start];
        backtracking(start+1, nums, remain, result);
        remain += nums[start];
    }
}

DFS + memo

T: O(t*n), t is target range (-2000 to 2000), n is nums length

S:O(t*n)

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        return dfs(0, nums, target, 0, new HashMap<>());
    }
    private int dfs(int start, int[] nums, int target, int sum, Map<String, Integer> memo) {
        if (start == nums.length) {
            if (sum == target) {
                return 1;
            }
            return 0;
        }
        String key = start + "," + sum;
        if (memo.containsKey(key)) {
            System.out.println("index, sum:" + key + ",value:" + memo.get(key));
            return memo.get(key);
        }
        int ways = dfs(start+1, nums, target, sum + nums[start], memo) + dfs(start+1, nums, target, sum - nums[start], memo);
        memo.put(key, ways);
        
        return ways;
    }
}

new one

```java
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        return dfs(nums, 0, target, new HashMap<>());
    }
    private int dfs(int[] nums, int i, int target, Map<String, Integer> memo) {
        if (i == nums.length && target == 0) {
            return 1;
        }
        String key = i + "_" + target;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
        int count = 0;
        if (i < nums.length) {
            count += dfs(nums, i+1, target - nums[i], memo);
            count += dfs(nums, i+1, target + nums[i], memo);
        }
        memo.put(key, count);
        return count;
    }
}
/*
base case:
sum == target

2 choice
[1,1,1,1,1]
/\
-+

*/
```