leetcode：698. 划分为k个相等的子集

题目

给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

提示：

  • 1 <= k <= len(nums) <= 16
  • 0 < nums[i] < 10000
  • 每个元素的频率在 [1,4] 范围内

示例：

  1. 输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
  2. 输出： True
  3. 说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。
输入: nums = [1,2,3,4], k = 3
输出: false

解答 & 代码

解法 0：递归回溯（超时）

class Solution {
private:
    /* 递归回溯，返回是否能将数组 nums 从下标 start 开始的部分划分为 k 个和为 target 的子集
       param nums: 数组
       param start: 数组的起始下标（前面的已经被分配到子集中）
       param k: 剩余待填充的子集数量
       param target: 每个子集的目标和
       param curVal: 当前填充的这个子集中已有元素的和
    */
    bool backTrace(vector<int>& nums, int start, int k, int target, int curVal)
    {
        // 递归结束条件：如果当前剩余待填充子集数为 0，说明已经成功划分，直接返回 true
        // 因为每个子集的目标和都是 target = sum/k，因此肯定恰好用完数组 nums 的所有元素
        if(k == 0)
            return true;

        bool isValid = false;
        // 从 start 开始遍历每个元素
        for(int i = start; i < nums.size(); ++i)
        {
            // 选择
            swap(nums[start], nums[i]);

            int newVal = curVal + nums[start];
            // 如果加上当前这个数，当前子集的元素和恰等于 target，则递归填充下一个子集
            if(newVal == target)
                isValid = isValid || backTrace(nums, start + 1, k - 1, target, 0);
            // 如果加上当前这个数，当前子集的元素和仍小于 target，则递归继续填充当前子集
            else if(newVal < target)
                isValid = isValid || backTrace(nums, start + 1, k, target, newVal);

            // 撤销选择
            swap(nums[start], nums[i]);
        }
        return isValid;
    }
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int len = nums.size();
        int sum = 0;
        for(int i = 0; i < len; ++i)
            sum += nums[i];

        if(sum % k != 0)
            return false;

        int target = sum / k;
        // cout << target << endl;
        return backTrace(nums, 0, k, target, 0);
    }
};

解法 1：递归回溯（剪枝）

class Solution {
private:
    /* 递归回溯，返回是否能将数组 nums 划分为 k 个和为 target 的子集
       param subSets: subSets[i] 存储的是子集 i 的元素和
       param setIdx: 当前填充的子集下标
       param nums: 数组
       param start: 数组的起始下标（前面的已经被分配到子集中）
       param target: 每个子集的目标和
       param used: used[i] 代表 nums[i] 是否已被使用
    */
    bool backTrace(vector<int>& subSets, int setIdx, vector<int>& nums, int start, int target, vector<bool>& used)
    {
        // 递归结束条件：如果当前已填充完所有子集，说明已经成功划分，直接返回 true
        // 因为每个子集的目标和都是 target = sum/k，因此肯定恰好用完数组 nums 的所有元素
        if(setIdx == subSets.size())
            return true;

        // 从 start 开始遍历每个元素，来填充子集 subSets[setIdx]
        for(int i = start; i < nums.size(); ++i)
        {
            // 剪枝：如果当前数字 nums[i] 已被使用，则跳过
            if(used[i] == true)
                continue;
            // 剪枝：如果当前数字 nums[i] 加入到当前子集后和大于 target，则跳过
            // 因为数组 nums 已按降序排列，后面的元素值更小，可能符合条件
            if(subSets[setIdx] + nums[i] > target)
                continue;

            // 选择
            subSets[setIdx] += nums[i];
            used[i] = true;

            bool isValid = false;
            // 如果加上当前这个数，当前子集的元素和恰等于 target，则递归填充下一个子集
            // 注意：这里调用递归函数，start 应设为 0 而不是 start + 1 ！！！！！！！
            // 因为要填充下一个子集，应该从头遍历数组，尝试所有未使用的元素
            if(subSets[setIdx] == target)
                isValid = backTrace(subSets, setIdx + 1, nums, 0, target, used);
            // 如果加上当前这个数，当前子集的元素和仍小于 target，则递归继续填充当前子集
            else
                isValid = backTrace(subSets, setIdx, nums, start + 1, target, used);
            if(isValid == true)
                return true;

            // 撤销选择
            subSets[setIdx] -= nums[i];
            used[i] = false;

            // 剪枝：当前子集初始为空，将数值 nums[i] 放入当前子集，最终无法得到一个满足题意的划分，
            // 因此在上面没有直接返回 true，而是撤销选择当前数值，元素和变回 0
            // 子集其实没有顺序，因此将当前数值 nums[i] 放入任何子集都无法得到满足题意的划分
            // 直接返回 false
            if(subSets[setIdx] == 0)
                return false;
        }
        return false;
    }
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int len = nums.size();
        int sum = 0;
        for(int i = 0; i < len; ++i)
            sum += nums[i]; 
        // 如果数组元素和不能被 k 整除，则直接返回 false
        if(sum % k != 0)
            return false;        
        int target = sum / k;        // 每个子集的目标和
        // 将数组从大到小排序
        sort(nums.begin(), nums.end(), greater<int>());
        // 如果数组最大元素超过了每个子集的目标和，那么直接返回 false
        if(nums[0] > target)
            return false;
        vector<int> subSets(k, 0);        // 存储 k 个子集的元素和，初始化为 0
        vector<bool> used(len, false);    // 存储每个元素值是否被使用
        return backTrace(subSets, 0, nums, 0, target, used);
    }
};

复杂度分析：设数组长为 N

  • 空间复杂度 O(N)：递归栈深度

执行结果：

执行结果：通过

执行用时：12 ms, 在所有 C++ 提交中击败了 70.72% 的用户
内存消耗：9.1 MB, 在所有 C++ 提交中击败了 55.72% 的用户