力扣-划分为k个相等的子集

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