416. Partition Equal Subset Sum

,

DFS

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
33
34
35
class Solution {
    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if ((sum & 1) == 1) {
            return false;
        }

        Set<Integer> memo = new HashSet<>();
        int targetSum = sum >> 1;
        return dfs(nums, 0, 0, targetSum, memo);
    }

    private boolean dfs(int[] nums, int startIndex, int currentSum, int targetSum, Set<Integer> memo) {
        if (memo.contains(currentSum * 201 + startIndex)) {
            return false;
        }
        if (currentSum == targetSum) {
            return true;
        }

        if (startIndex < nums.length && currentSum < targetSum) {
            // choose
            if (dfs(nums, startIndex + 1, currentSum + nums[startIndex], targetSum, memo)) {
                return true;
            }
            // not choose
            if (dfs(nums, startIndex + 1, currentSum, targetSum, memo)) {
                return true;
            }
        }

        memo.add(currentSum * 201 + startIndex);
        return false;
    }
}

DP

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
33
class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        int maxNum = Integer.MIN_VALUE;
        for (int num : nums) {
            sum += num;
            maxNum = Math.max(maxNum, num);
        }

        int targetSum = sum >> 1;
        if ((sum & 1) == 1 || maxNum > targetSum) {
            return false;
        }

        // 定义 dp[i][j] 从 nums 前 i 个元素中任意选择一些元素是否能组成和 j
        // dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[0...i - 1]]
        boolean[][] dp = new boolean[nums.length + 1][targetSum + 1];
        for (int i = 0; i <= nums.length; i++) {
            dp[i][0] = true; // 从前 i 个元素中选择 0 个元素时都能组成和 0
        }

        for (int i = 1; i <= nums.length; i++) {
            for (int j = 1; j <= targetSum; j++) {
                dp[i][j] = dp[i - 1][j]; // 不选择当前元素
                if (!dp[i][j] && j - nums[i - 1] >= 0) {
                    dp[i][j] |= dp[i - 1][j - nums[i - 1]];
                }
            }
        }

        return dp[nums.length][targetSum];
    }
}

DP

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 {
    public boolean canPartition(int[] nums) {
        if (nums.length < 2) {
            return false;
        }

        int maxNum = Integer.MIN_VALUE;
        int sum = 0;
        for (int num : nums) {
            sum += num;
            maxNum = Math.max(maxNum, num);
        }

        int targetSum = sum >> 1;
        if ((sum & 1) == 1 || maxNum > targetSum) {
            return false;
        }

        boolean[] dp = new boolean[targetSum + 1];
        dp[0] = dp[nums[0]] = true;

        for (int i = 1; i < nums.length; i++) {
            for (int j = targetSum; j >= 1; j--) { // 注意此处倒序，因为 dp[j] depends on dp[j - nums[i]], 为了防止状态被覆盖
                if (j - nums[i] >= 0) {
                    dp[j] = dp[j] | dp[j - nums[i]];
                }
            }
        }

        return dp[targetSum];
    }
}

References

416. Partition Equal Subset Sum
剑指 Offer II 101. 分割等和子集