LeetCode 126. 划分为k个相等的子集
原题链接
中等
作者:
あ
,
2022-01-10 15:02:50
,
所有人可见
,
阅读 132
DFS+略微剪枝
思路
见: https://leetcode-cn.com/problems/partition-to-k-equal-sum-subsets/solution/hua-fen-kge-xiang-deng-zi-ji-shen-du-you-ozap/
代码
class Solution {
public:
int n,visit[20],s;
bool dfs(vector<int>& nums,int k,int temp,int now)//now是指从当前位置开始继续往后进行选择,这不是全排列,没必要每次都从0开始选
{
if(temp==s)
{
k--;
if(k==0)
return true;
return dfs(nums,k,0,0);
}
for(int i=now;i<n;i++)
{
if(!visit[i]&&temp+nums[i]<=s)//得加个temp+nums[i]<=s进行剪枝
{
visit[i]=1;
if(dfs(nums,k,temp+nums[i],now+1))
return true;
visit[i]=0;
}
}
return false;
}
bool canPartitionKSubsets(vector<int>& nums, int k) {
n=nums.size();
int sum=0;
for(int i=0;i<n;i++)
sum+=nums[i];
s=sum/k;
if(s*k!=sum)
return false;
return dfs(nums,k,0,0);
}
};