划分为k个相等的子集

问题描述 :

给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

示例 1：

输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4

输出： True

说明：有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。

输入说明 :

首先输入nums数组的长度n，

然后输入n个整数，以空格分隔。

最后输入k。

1 <= k <= n <= 16

0 < nums[i] < 10000

输出说明 :

输出true或false

输入范例 :

7
4 3 2 3 5 2 1
4

输出范例 :

true

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 class Solution {
 4 public:
 5     bool dfs(vector<int>& groups, int index, vector<int>& nums, int target)
 6     {
 7         if (!index)return true;
 8         int val = nums[--index];
 9         for (int i = 0; i < groups.size(); i++)
10         {
11             if (groups[i] + val <= target)
12             {
13                 groups[i] += val;
14                 if (dfs(groups, index, nums, target))return true;
15                 groups[i] -= val;
16             }
17             if (!groups[i])break;//每次都保证0值只出现在 group的末尾 
18             //例如一个数放在哪个group里都是一样的 所以优先放前面的筐
19         }
20         return false;
21     }
22     bool canPartitionKSubsets(vector<int>& nums, int k) {
23         int num_size = nums.size(), sum = 0, target;
24         for (auto i : nums)sum += i;
25         if (sum % k)return false;
26         target = sum / k;
27         sort(nums.begin(), nums.end());
28         if (nums[num_size - 1] > target)return false;
29         while (num_size && nums[num_size - 1] == target) { num_size--; k--; }
30         if (!num_size)return true;
31         vector<int> group(k, 0);//这里是大小是k 因为要分成k组
32         return dfs(group, num_size, nums, target);
33     }
34 };
35 /*
36 7
37 2 2 2 2 3 4 5
38 4
39 */
40 int main()
41 {
42     int n, data,k;
43     vector<int> vec;
44     cin >> n;
45     for (int i = 0; i < n; i++)
46     {
47         cin >> data;
48         vec.push_back(data);
49     }
50     cin >> k;
51     bool res = Solution().canPartitionKSubsets(vec,k);
52     if (res)cout << "true";
53     else cout << "false";
54     return 0;
55 }