Description Link to heading

698.partition-to-k-equal-sum-subsets

Solution Link to heading

Sort array from large to small, so that we can avoid making mistake of judging arrays like [1, 1, 2, 2].

We use used[i] to avoid using the same element more than once, if sum == target, sum = 0, if cnt == k, than it can be devided.

Code Link to heading 

class Solution {
  public:
    bool dfs(vector<int> &nums, int index, int sum, int target, int cnt, int k, vector<int> &used, int idx) {
        if (cnt == k)
            return true;
        if (sum == target) {
            return dfs(nums, idx - 1, 0, target, cnt + 1, k, used, idx - 1); // pay attention to the `idx - 1` rather than `index - 1`
        }

        for (int i = index; i >= 0; i--) {
            if (used[i] || sum + nums[i] > target)
                continue;
            used[i] = 1;
            if (dfs(nums, i - 1, sum + nums[i], target, cnt, k, used, idx))
                return true;
            used[i] = 0;
            if (sum == 0)
                return false;
        }
        return false;
    }
    bool canPartitionKSubsets(vector<int> &nums, int k) {
        int sum = 0;
        for (int i : nums)
            sum += i;
        if (sum % k != 0)
            return false;
        std::sort(nums.begin(), nums.end());
        if (nums.back() > sum / k)
            return false;
        vector<int> used(nums.size(), 0);
        return dfs(nums, nums.size() - 1, 0, sum / k, 0, k, used, nums.size() - 1);
    }
};