Description
Given an integer array \(nums\) and an integer \(k\), return true if it is possible to divide this array into \(k\) non-empty subsets whose sums are all equal.
Constraints
- \(1 \le k \le nums.length \le 16\)
- \(1 \le nums_i \le 10^4\)
- The frequency of each element is in the range \([1, 4]\)
Solution
状压可达性DP
Code
class Solution {
public:
bool canPartitionKSubsets(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
long sum = 0;
for(auto v : nums) sum += v;
if(sum % k) return false;
long d = sum / k;
auto dfs = [&nums, d, dp = vector<char>(1<<nums.size(), 1)]
(auto &&f, int S, int sum) mutable -> bool {
if(!S) return true;
if(!dp[S]) return false;
for(int i = 0; i < nums.size(); ++i) {
if(nums[i] + sum > d) break;
if(S >> i & 1) {
int v = nums[i] + sum;
if(v == d) v = 0;
if(f(f, S ^ (1<<i), v)) {
return true;
}
}
}
return dp[S] = false;
};
return dfs(dfs, (1<<nums.size())-1, 0);;
}
};