/*
 * @lc app=leetcode.cn id=698 lang=cpp
 *
 * [698] 划分为k个相等的子集
 */

// @lc code=start
class Solution {
private:
    vector<int> bucket;

    bool backtrack(vector<int>& nums, int index, int target) {
        if (index == nums.size()) return true;

        for (int i = 0; i < bucket.size(); ++i) {
            if (nums[index] + bucket[i] > target) continue;
            if (i > 0 && bucket[i] == bucket[i - 1]) continue;
            bucket[i] += nums[index];
            if (backtrack(nums, index + 1, target)) return true;
            bucket[i] -= nums[index];
        }
        return false;
    }

public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (k > nums.size()) return false;
        if (sum % k != 0) return false;
        
        sort(nums.rbegin(), nums.rend());

        bucket.resize(k);
        int target = sum / k;
        
        return backtrack(nums, 0, target);
    }
};
// @lc code=end