Skip to content

698. Partition to K Equal Sum Subsets 👍

  • Time: $O(2^n)$
  • Space: $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
29
30
31
32
33
class Solution {
 public:
  bool canPartitionKSubsets(vector<int>& nums, int k) {
    const int sum = accumulate(begin(nums), end(nums), 0);
    if (sum % k != 0)
      return false;

    const int t = sum / k;  // each subset's target sum
    return dfs(nums, 0, k, t, t, vector<bool>(nums.size()));
  }

 private:
  bool dfs(const vector<int>& nums, int s, int k, int target,
           const int subsetTargetSum, vector<bool>&& seen) {
    if (k == 0)
      return true;
    if (target < 0)
      return false;
    if (target == 0)
      return dfs(nums, 0, k - 1, subsetTargetSum, subsetTargetSum, move(seen));

    for (int i = s; i < nums.size(); ++i) {
      if (seen[i])
        continue;
      seen[i] = true;
      if (dfs(nums, i + 1, k, target - nums[i], subsetTargetSum, move(seen)))
        return true;
      seen[i] = false;
    }

    return false;
  }
};

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

    final int t = sum / k; // each subset's target sum
    boolean[] seen = new boolean[nums.length];
    return dfs(nums, 0, k, t, t, seen);
  }

  private boolean dfs(int[] nums, int s, int k, int target, int subsetTargetSum, boolean[] seen) {
    if (k == 0)
      return true;
    if (target < 0)
      return false;
    if (target == 0)
      return dfs(nums, 0, k - 1, subsetTargetSum, subsetTargetSum, seen);

    for (int i = s; i < nums.length; ++i) {
      if (seen[i])
        continue;
      seen[i] = true;
      if (dfs(nums, i + 1, k, target - nums[i], subsetTargetSum, seen))
        return true;
      seen[i] = false;
    }

    return false;
  }
}