给你一个数组 nums 和正整数 k，请你判断 nums 是否能被平分为元素和相同的 k 个子集。
函数签名如下：

bool canPartitionKSubsets(vector& nums, int k);

思路分析

把装有 n 个数字的数组 nums 分成 k 个和相同的集合，可以想象成将 n 个数字分配到 k 个「桶」里，最后，这 k 个「桶」里的数字之和要相同。回溯算法的关键在于要知道怎么「做选择」，这样才能利用递归函数进行穷举。
将 n 个数字分配到 k 个桶里，可以有两种视角：

  • 视角一：如果切换到这 n 个数字的视角，每个数字都要选择进入到 k 个桶中的某一个；
  • 视角二：如果切换到这 k 个桶的视角，对于每个桶，都要遍历 nums 中的 n 个数字，然后选择是否将当前遍历到的数字装进自己这个桶里。

用不同的视角进行穷举，虽然结果相同，但是解法代码的逻辑完全不同。

以数字视角

  1.  // 递归穷举 nums 中的每个数字
  2. bool backtrack(vector<int>& nums, int index, vector<int>& bucket, int target) {
  3.     if (index == nums.size()) {
  4.         // 检查所有桶的数字之和是否都是 target
  5.         for (int i = 0; i < bucket.size(); ++i) {
  6.             if (bucket[i] != target) {
  7.                 return false;
  8.             }
  9.         }
  10.         // nums 成功平分成 k 个子集
  11.         return true;
  12.     }
  14.     // 穷举 nums[index] 可能装入的桶
  15.     for (int i = 0; i < bucket.size(); ++i) {
  16.         // 剪纸，桶装满了
  17.         if (bucket[i] + nums[index] > target) {
  18.             continue;
  19.         }
  20.         //  将 nums[index] 装入 bucket[i]
  21.         bucket[i] += nums[index];
  22.         // 递归穷举下一个数字的选择
  23.         if (backtrack(nums, index + 1, bucket, target)) {
  24.             return true;
  25.         }
  26.         // 撤销选择
  27.         bucket[i] -= nums[index];
  28.     }
  29.     // nums[index] 装入哪个桶都不行
  30.     return false
  31. }
  33. // 主函数
  34. bool canPartitionKSubsets(vector<int>& nums, int k) {
  35.     // 排除一些基本情况
  36.     if (k > nums.size()) {
  37.         return false
  38.     }
  39.     int sum = 0;
  40.     for (int v : nums) {
  41.         sum += v;
  42.     }
  43.     if (sum % k != 0) {
  44.         return fasle
  45.     }
  46.     // k 个桶，记录每个桶装的数字之和
  47.     vector<int> bucket(k, 0);
  48.     // 理论上每个桶中数字之和
  49.     int target = sum / k;
  50.     // 穷举
  51.     return backtrack(nums, 0, bucket, target);
  52. }

如果能够让尽可能多的情况命中剪枝那个 if 分支，就可以减少递归调用的次数，一定程度上减少了时间复杂度。
如何尽可能多的命中这个 if 分支？index 参数是从 0 开始的，也就是递归从 0 开始遍历 nums 数组。
如果提前对这个 nums 数组排序，把大的数字排在前面，那么大的数字会先被分配到 bucket 中，对于之后的数字，bucket[i] + nums[index] 会更大，更容易触发剪枝的 if 条件。
所以，可以在之前的代码中再添加一些代码：

bool canPartitionKSubsets(vector<int>& nums, int k) {
    // 其他代码不变
    // 降序排序 nums 数组
    sort(nums.begin(), nums.end(), cmp);
    return backtrack(nums, 0, bucket, target)
} 
static bool cmp(int a, int b) {
    return a > b;
}

以桶的视角

以桶的视角进行穷举，每个桶都要遍历 nums 中的所有数字，决定是否把当前数字装进桶中；当装满一个桶之后，还要装下一个桶，直到所有桶都装满为止。

bool backtrack(int k, int bucket, vector<int>& nums, int start, vector<bool>& used, int target) {
    // base case
    if (k == 0) {
        // 所有桶都被装满了，而且 nums 一定用完了
        return true;
    }
    if (bucket == target) {
        // 当前桶装满了，递归穷举下一个桶的选择，让下一个桶从 nums[0] 开始选数字
        return backtrack(k - 1, 0, nums, 0, used, target);
    }

    // 从 start 开始向后探查有效的 nums[i] 装入当前桶
    for (int i = start; i < nums.size(); ++i) {
        // 剪枝
        if(used[i]) {
            // nums[i] 被装进别的桶
            continue;
        }
        if (nums[i] + bucket > target) {
            // 当前桶装不下 nums[i]
            continue;
        }
        // 做选择，将 nums[i] 装入当前桶中
        used[i] = true;
        bucket += nums[i];
        // 递归穷举下一个数字是否装入当前桶
        if (backtrack(k, bucket, nums, i + 1, used, target) {
            return true;
        }
        // 撤销选择
        used[i] = false;
        bucket -= nums[i];
    }
    // 穷举了所有数字，无法装满当前桶
    return false;
}

总结

这两个算法的时间复杂度，假设 nums 中的元素个数为 n。
先说第⼀个解法，也就是从数字的⻆度进⾏穷举，n 个数字，每个数字有 k 个桶可供选择，所以组合出的结果个数为 k^n，时间复杂度也就是 O(k^n)。
第⼆个解法，每个桶要遍历 n 个数字，选择「装⼊」或「不装⼊」，组合的结果有 2^n 种；⽽我们有 k 个桶，所以总的时间复杂度为 O(k*2^n)。