LeetCode Solutions
698. Partition to K Equal Sum Subsets
Time: $O(2^n)$ Space: $O(n)$
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;
}
};
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;
}
}