# Partition to K Equal Sum Subsets

Oct 29, 2017

Given an array of integers nums and a positive integer k, find whether it’s possible to divide this array into k non-empty subsets whose sums are all equal.

Example 1: Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4 Output: True Explanation: It’s possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums. Note:

1 <= k <= len(nums) <= 16. 0 < nums[i] < 10000.

btw,这里好像没有制表啊，然后我还一直想着要怎么制表。算了，明天还是按顺序直接刷吧。

bool canPartitionKSubsets(vector<int>& nums, int k) {
if ( k <= 1 ) return true;
//return canPartitionKSubsets(nums.begin(),k/2);

sort(nums.begin(),nums.end());

int sum = 0;
for(auto i:nums)
sum +=i;
if (sum % k != 0) return false;
int a = sum / k;
vector<int> kdq(k,a);
return possible(nums,kdq,nums.size() - 1);
}
bool possible(vector<int> &nums,vector<int> &kdq,int index) {
if (index < 0) {
for(int i:kdq) if (i != 0) return false;
return true;
}
int n = nums[index];
for(auto &a:kdq) {
if (a >= n) {
a -= n;
if (possible(nums,kdq,index-1)) return true;
a += n;
}
}
return false;
}

LeetCodeLeetCodeDP