Partition to K Equal Sum Subsets

LeetCode
,

第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
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
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;
}