Leetcode 698: Partition to K Equal Sum Subsets

https://leetcode.com/problems/partition-to-k-equal-sum-subsets/description/

Notes:

This question can be viewed as a follow up of Leetcode 416.

However, we cannot apply knapsack method to this question when k > 2, since we need to remember which elements have been chosen, then continue the search until all the elements can be grouped with the sum required.

So it is a typical back-tracking problem.

See the code below:

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        if(nums.size() < k) return false;
        int sum = 0;
        for(auto &a : nums) sum += a;
        if(sum%k != 0) return false;
        sort(nums.begin(), nums.end());
        if(nums.back()>sum/k) return false;
        reverse(nums.begin(), nums.end());
        vector<bool> visit(nums.size(), false);
        return dsf(nums, visit, sum/k, k, 0);
    }
private:
    bool dsf(vector<int>& ns, vector<bool>& visit, int s, int k, int ac){
        if(k==0) return true;
        if(ac == s) return dsf(ns, visit, s, k-1, 0);
        for(int i=0; i<ns.size(); ++i){
            if(visit[i]) continue;
            if(ac + ns[i] > s) break;
            visit[i] = true;
            if(dsf(ns, visit, s, k, ac+ns[i])) return true;
            visit[i] = false;
        }
        return false;
    }
};