698. Partition to K Equal Sum Subsets

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
36
37
38
class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = Arrays.stream(nums).sum();
        if (sum % k != 0) {
            return false;
        }

        int targetSum = sum / k;
        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        return dfs(nums, used, nums.length - 1, 0, targetSum, k);
    }

    private boolean dfs(int[] nums, boolean[] used, int startIndex, int sum, int targetSum, int k) {
        if (k == 1) {
            // 当剩余最后一个集合时，无需遍历到底
            return true;
        }

        if (sum == targetSum) {
            return dfs(nums, used, nums.length - 1, 0, targetSum, k - 1);
        }

        for (int i = startIndex; i >= 0; i--) {
            if (used[i] || sum + nums[i] > targetSum || (i + 1 < nums.length && !used[i + 1] && nums[i] == nums[i + 1])) {
                continue;
            }

            used[i] = true;
            if (dfs(nums, used, i - 1, sum + nums[i], targetSum, k)) {
                return true;
            }
            used[i] = false;
        }

        return false;
    }
}

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
class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = Arrays.stream(nums).sum();
        if (sum % k != 0) {
            return false;
        }

        int targetSum = sum / k;
        Arrays.sort(nums);
        int[] collections = new int[k];
        return dfs(nums, nums.length - 1, targetSum, collections);
    }

    private boolean dfs(int[] nums, int index, int targetSum, int[] collections) {
        if (index == -1) {
            return true;
        }

        for (int i = 0; i < collections.length; i++) {
            if (collections[i] + nums[index] > targetSum || (i > 0 && collections[i] == collections[i - 1])) {
                continue;
            }

            collections[i] += nums[index];
            if (dfs(nums, index - 1, targetSum, collections)) {
                return true;
            }
            collections[i] -= nums[index];
        }

        return false;
    }
}

References

698. Partition to K Equal Sum Subsets