1.问题描述
给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
示例 1：
输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
输出： True
2.说明
有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。
输入说明：
首先输入nums数组的长度n，
然后输入n个整数，以空格分隔。
最后输入k。
1 <= k <= n <= 16
0 < nums[i] < 10000
输出说明：
输出true或false
3.范例
输入：
7
4 3 2 3 5 2 1
4
输出：
true
4.思路
k个非空子集综合都相等，即在nums数组元素的总和除以k就是各个子集的和，设各个子集的和为：subsum，遍历数组，找到元素和为subnum的子集。
通过mark标记已经遍历过的元素，放止重复遍历。
5.代码
#include <iostream> #include <vector> #include <stdio.h> using namespace std; class Solution { public: bool subset(vector<int> &nums,int k) { int len=nums.size(); if(len<k) return false; int sum=0; for(int i=0;i<nums.size();i++) sum +=nums[i]; if(sum%k!=0) return false; vector<int> mark(len,0);//标记数字是否已被选中,初始化为0 return get_k_subset(nums,mark,sum/k,0,0,k); } private: bool get_k_subset(vector<int> &nums,vector<int> &mark, int subsum,int cursum,int start,int k) //subsum=sum/k;//每个子集的和 //cursum;//表示当前子集和 //start;//表示数组从start位置开始查找 { if(k==1) return true; if(cursum==subsum) return get_k_subset(nums,mark,subsum,0,0,k-1); for(;start<nums.size();start++) { if(mark[start]==1) //1时，表示被标记过 continue; mark[start]=1; if(get_k_subset(nums,mark,subsum,cursum+nums[start],start+1,k)) return true; mark[start]=0; } return false; } }; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); Solution solve; int n; cin>>n; vector<int> nums; int data; for(int i=0;i<n;i++) { cin>>data; nums.push_back(data); } int k; cin>>k; bool res=solve.subset(nums,k); cout<<(res? "true":"false")<<endl; return 0; }