题目描述

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.

算法1

(DFS+backtracking) $O(2^n)$

将数组降序排序，进行k段分割的dfs，当cursum累加等于target时，对下一段开始分割，期间用visit数组记录访问过的元素。dfs中加入减枝以降低搜索复杂度，当cursum>target直接返回false，

时间复杂度

排列组合，O(2^n)
visit数组O（n）

参考文献

C++ 代码

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum=accumulate(nums.begin(), nums.end(),0);
        if(sum%k!=0) return false;
        sort(nums.rbegin(),nums.rend());
        vector<bool> visit(nums.size(),false);
        return helper(nums, k, sum/k, 0,0,visit);
    }
    bool helper(vector<int>&nums, int k, int target, int start, int cursum, 
                vector<bool> &visit)
    {
        if(k==1) return true;
        if(cursum>target) return false;
        if(cursum==target) return helper(nums, k-1, target, 0, 0, visit);
        for(int i=start;i<nums.size();i++)
        {
            if(visit[i]) continue;
            visit[i]=true;
            if(helper(nums,k, target, i+1, cursum+nums[i], visit)) return true;
            visit[i]=false;
        }
        return false;
    }
};