第35天。

又一次一个早上没做出来，难道要跪在DP上了吗？

今天的题目是Partition to K Equal Sum Subsets:

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.

虽然一开始思路是对的，但是就是没想出来做递归，先讲讲我想到的：

首先，他要我们分辨一组数字是否能被划分成K个相同的子集，我们可以对这个数组进行求和，如果和是K的倍数，那么这个倍数a就是每个子集的和，如果不是K的倍数，则肯定没法分成和相同的K个子集。

现在问题变成了，找出k个子集使得它的和为a.

然后，我就不会做了。

然后是在dicuss中看到的方法，前面的思路是完全一样的，所以这里只讲讲他是怎么做求出k个子集使得和为a的.

其实方法很简单，暴力搜而已。

我们用一个大小为k的vector来记录每个子集的和（或者还差多少），然后我们从后面向前搜索，每次尝试将一个元素放入第i个vector中，然后考虑下一个元素，emmm，其实不好讲出来，但是代码挺简单的。

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

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

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

7
    int sum = 0;
8
    for(auto i:nums)
9
        sum +=i;
10
    if (sum % k != 0) return false;
11
    int a = sum / k;
12
    vector<int> kdq(k,a);
13
    return possible(nums,kdq,nums.size() - 1);
14
}
15
bool possible(vector<int> &nums,vector<int> &kdq,int index) {
14 collapsed lines
16
    if (index < 0) {
17
        for(int i:kdq) if (i != 0) return false;
18
        return true;
19
    }
20
    int n = nums[index];
21
    for(auto &a:kdq) {
22
        if (a >= n) {
23
            a -= n;
24
            if (possible(nums,kdq,index-1)) return true;
25
            a += n;
26
        }
27
    }
28
    return false;
29
}