题目描述

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

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

平均切分数组，用dfs解决，剪枝和边界条件的顺序要注意。略恶心

C++ 代码

class Solution {
public:
vector<bool> visited;
    int sz;
    bool ans = false;
    int target;
    bool dfs(vector<int>&nums,int id,int cur,int k){
         if(k==0){
           return true;
        }
        if(cur==target){
            return dfs(nums,0,0,--k);
        }
        for(int i = id;i<sz;i++){
            if(visited[i])continue;
            visited[i] = true;
            if(cur+nums[i]<=target){
                if(dfs(nums,i+1,cur+nums[i],k))return true;
            }
            visited[i] = false;
        }
        return false;
    }

    bool canPartitionKSubsets(vector<int>& nums, int k) {
        sz = nums.size();
        visited = vector<bool>(sz);
        int sum = accumulate(nums.begin(),nums.end(),0);
        if(sum%k!=0)return false;
        target = sum/k;
        return dfs(nums,0,0,k);;
    }
};