LC.P494[目标和]

方法一：回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {

    int ans, target, n;
    int[] nums;

    public int findTargetSumWays(int[] nums, int target) {
        this.nums = nums;
        this.n = nums.length;
        this.target = target;
        dfs(0, 0);
        return ans;
    }

    private void dfs(int index, int sum) {
        if (index == n) {
            if (sum == target) ++ans;
        } else {
            dfs(index + 1, sum + nums[index]);
            dfs(index + 1, sum - nums[index]);
        }
    }
}
  • 时间复杂度：$O(2^n)$
  • 空间复杂度：$O(n)$

方法二：记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {

    int target, n;
    int[] nums;
    Map<String, Integer> cache;

    public int findTargetSumWays(int[] nums, int target) {
        this.nums = nums;
        this.n = nums.length;
        this.target = target;
        cache = new HashMap<>();
        return dfs(0, 0);
    }

    private int dfs(int index, int sum) {
        String key = index + "_" + sum;
        if (cache.containsKey(key)) return cache.get(key);
        if (index == n) {
            cache.put(key, sum == target ? 1 : 0);
            return cache.get(key);
        } else {
            int left = dfs(index + 1, sum + nums[index]);
            int right = dfs(index + 1, sum - nums[index]);
            cache.put(key, left + right);
            return cache.get(key);
        }
    }
}
  • 时间复杂度：$O(n \times \sum_{i = 0}^{n - 1}abs(nums[i]))$
  • 空间复杂度：$O(n \times \sum_{i = 0}^{n - 1}abs(nums[i]))$

方法三：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length, offset = 0;
        for (int num : nums) offset += Math.abs(num);
        if (Math.abs(target) > offset) return 0;
        int[][] f = new int[n + 1][2 * offset + 1];
        f[0][offset] = 1;
        for (int i = 1; i <= n; ++i) {
            int num = nums[i - 1];
            for (int j = -offset; j <= offset; ++j) {
                if (j - num + offset >= 0) f[i][j + offset] += f[i - 1][j - num + offset];
                if (j + num + offset <= 2 * offset) f[i][j + offset] += f[i - 1][j + num + offset];
            }
        }
        return f[n][target + offset];
    }
}
  • 时间复杂度：$O(n \times \sum_{i = 0}^{n - 1}abs(nums[i]))$
  • 空间复杂度：$O(n \times \sum_{i = 0}^{n - 1}abs(nums[i]))$

方法四：动态规划(优化)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length, s = 0;
        for (int num : nums) s += Math.abs(num);
        if (target > s || (s - target) % 2 != 0) return 0;
        int m = (s - target) / 2;
        int[][] f = new int[n + 1][m + 1];
        f[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            int num = nums[i - 1];
            for (int j = 0; j <= m; ++j) {
                f[i][j] += f[i - 1][j];
                if (j >= num) f[i][j] += f[i - 1][j - num];
            }
        }
        return f[n][m];
    }
}
  • 时间复杂度：$O(n \times \sum_{i = 0}^{n - 1}abs(nums[i] - target))$
  • 空间复杂度：$O(n \times \sum_{i = 0}^{n - 1}abs(nums[i] - targ))$