# leetcode 698. Partition to K Equal Sum Subsets 分支限界

#### 题目

https://leetcode.com/problems/partition-to-k-equal-sum-subsets/
Given an array of integers nums and a positive integer k, find whether it’s possible to divide this array into k non-empty subsets whose sums are all equal.

Example 1:

Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
Output: True
Explanation: It’s possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Note:

1 <= k <= len(nums) <= 16.
0 < nums[i] < 10000.

#### 思路

dfs 分支限界直接回溯，dfs实际上是考虑到了所有的组合的，所以不用担心排列组合导致的无法划分为k个子集的情况，代码中的 flag 标志计算使用 dfs 递归遍历所有组合

#### 源码

``````class Solution {
public:
int avg;
bool canPartitionKSubsets(vector<int>& nums, int k) {
int sum = 0;
for(auto p:nums){
sum+=p;
}
if(sum % k !=0) return false;
avg =  sum / k;
vector<bool> vis(nums.size(),false);
return dfs(nums.size()-1,avg,nums,nums.size(),vis);
}
bool dfs(int start,int target,vector<int> &nums,int remains,vector<bool> &vis){
if(remains==0)return true;
bool flag = false;
for(int i = start;i >= 0;--i){
if(!vis[i]&&target>=nums[i]){
vis[i]=true;
if(target == nums[i])flag = dfs(nums.size()-1,avg,nums,remains-1,vis);
else flag = dfs(i-1,target-nums[i],nums,remains-1,vis);
if(flag)return flag;
vis[i]=false;
// while(i>=1&&nums[i]==nums[i-1])i--;
}
}
return flag;
}
};
``````