32 划分为k个相等的子集(698)

作者: Turbo时间限制: 1S章节: 递归

晚于: 2020-07-29 12:00:00后提交分数乘系数50%

截止日期: 2020-08-05 12:00:00

问题描述 :

给定一个整数数组  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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) 
    {
        int len=nums.size(),sum=0;
        for(auto i:nums)
            sum+=i;//计算总和 
        if(sum%k)//不能整除，肯定不能成功划分 
            return false;
        sum=sum/k;//sum为划分后的各个子集总和 
        sort(nums.begin(),nums.end());//从小到大排序 
        if(nums[len-1]>sum)//最大的数比总和大，也不能划分 
            return false;
        while(len&&nums[len-1]==sum)//把所有等于sum的数单独放入一个组里面
        {
            len--;
            k--;
        }
        if(!len)
            return true;
        vector<int> depart(k,0);
        dfs(depart,len,nums,sum);
        
    }
private:
    bool dfs(vector<int> &depart,int len,vector<int> &nums,int sum)
    {
        if(!len)
            return true;
        int val=nums[--len];
        for(int i=0;i<depart.size();i++)
        {
            if(depart[i]+val<=sum)
            {
                depart[i]+=val;
                if(dfs(depart,len,nums,sum))
                    return true;
                depart[i]-=val;
            }    
        }
        return false; 
    }
};

int main()
{
    int n,data;
    vector<int> nums;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>data;
        nums.push_back(data);
    }
    int k;
    cin>>k;
    if(bool res=Solution().canPartitionKSubsets(nums,k))
        cout<<"true";
    else
        cout<<"false";
    return 0;
}