698.partition-to-k-equal-sum-subsets 划为k个相等的子集

问题描述

698.划为k个相等的子集

解题思路

首先，对数组按照从大到小排序，相比从小到大排序，能避免[1, 1, 2, 2]这样的数组的误判;

利用used[i]数组避免重复使用同一个元素，如果sum == target，就将sum置零，如果cnt == k，说明满足条件。

代码

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); //注意这里是idex - 1而不是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);
    }
};