[Leetcode]698.Partition to K Equal Sum Subsets

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

示例 1：
输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
输出： True
说明：有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。

相关标签：深度优先搜索

通过深度优先搜索即可解决。关键点是，当我们在找形成target的子数组时，要首先考虑数组中大的数，因为如果小的数能组成大数，那么首先利用大数可以避免后面的小数用完，大数无法组成target的情况。想通这一点，其实这道题就能通过常规方法解决了。

其代码如下：

python:

class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        sum_ = sum(nums)
        if sum_%k or max(nums)>sum_//k:return False
        nums.sort(reverse=True)
        return self.dfs(nums,sum_//k,sum_//k)

    def dfs(self,nums,cur,target):
        if not nums and not cur:return True
        if not cur:
            cur = target
        for i in range(len(nums)):
            if cur >= nums[i]:
                rest = nums[:i]+nums[i+1:]
                if self.dfs(rest,cur-nums[i],target):
                    return True
        return False

C++:

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum_ = accumulate(nums.begin(),nums.end(),0);
        if(sum_%k!=0 || *max_element(nums.begin(),nums.end())>sum_/k) return false;
        sort(nums.begin(),nums.end(),greater<int>());
        int target = sum_/k;
        return dfs(nums,target,target);
    }

    bool dfs(vector<int> &nums,int cur,int target){
        if(nums.empty() && cur==0){return true;}
        if(cur==0) {
            cur=target;
        }
        for(int i=0;i<nums.size();++i){
            if(cur>=nums[i]){
                vector<int> rest;
                for(int j=0;j<nums.size();++j){
                    if(j!=i){rest.push_back(nums[j]);}
                }
                if(dfs(rest,cur-nums[i],target)){return true;}
            }
        }
        return false;
    }
};

[Leetcode]698.Partition to K Equal Sum Subsets

相关推荐