LC.P416[分割等和子集]

方法一：记忆化搜索

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
29
30
31
32
class Solution {
    private int[][] cache;
    private int[] nums;
    private int n;

    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) sum += num;
        if (sum % 2 != 0) {
            return false;
        }
        this.n = nums.length;
        this.nums = nums;
        cache = new int[n][sum / 2 + 1];
        for (int[] c : cache) {
            Arrays.fill(c, -1);
        }
        return dfs(0, sum / 2);
    }

    private boolean dfs(int i, int s) {
        if (i >= n) {
            return s == 0;
        }
        if (cache[i][s] != -1) {
            return cache[i][s] == 1;
        }
        boolean res = (s >= nums[i] && dfs(i + 1, s - nums[i])) || dfs(i + 1, s);
        cache[i][s] = res ? 1 : 0;
        return res;
    }
}
  • 时间复杂度：$O(ns)$，其中$n$是数组的长度，$s$是数组和的一半
  • 空间复杂度：$O(ns)$。保存多少状态，就需要多少空间。

方法二：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public boolean canPartition(int[] nums) {
        int s = 0;
        for (int num : nums) {
            s += num;
        }
        if (s % 2 != 0) {
            return false;
        }
        s /= 2;
        int n = nums.length;
        boolean[][] f = new boolean[n + 1][s + 1];
        f[0][0] = true;
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            for (int j = 0; j <= s; j++) {
                f[i + 1][j] = (j >= x && f[i][j - x]) || f[i][j];
            }
        }
        return f[n][s];
    }
}
  • 时间复杂度：$O(ns)$
  • 空间复杂度：$O(ns)$