经典回溯算法：集合划分问题 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：经典回溯算法：集合划分问题

评论礼仪 见这里，违者直接拉黑。

[0xlightyear]

@luckywords 我感觉你的解法和东哥那个遍历数字解法本质是一样的。你尝试对nums排序了吗？

[zhuifengshaonian201]

我是发现了，我脑袋不够用

[zhuifengshaonian201]

看着是感觉自己好像懂了，实际上这类型题还是找不到头绪

[Qiqiqiqiqishuo]

@luckywords @0xlightyear
我用的C语言，遍历数字解法，不对nums排序85/155时间超限，降序后155/150时间超限😭

[labuladong]

@luckywords @0xlightyear @Qiqiqiqiqishuo
可能是力扣测试用例更新了，之前的代码确实可能超时。我在文章中更新了优化的方案，通过备忘录和位图技巧进一步提高算法的效率。

[52KunKun]

不好意思 想问一下代码上的一些不理解的地方，我想问一下站在桶的角度上看问题，保存used状态发生在一个桶装满的情况下，可为什么剪枝的时候判断情况是任意情况（我的意思是尽管桶是否被装满都可以进行剪枝判断），这个剪枝判断不应该发生在一个桶被装满的情况上吗？

[zhao2019010704]

for (int i = 0; i < bucket.length; i++) {
        // 剪枝，桶装装满了
        if (bucket[i] + nums[index] > target) {
            continue;
        }
        // 将 nums[index] 装入 bucket[i]
        bucket[i] += nums[index];
        // 递归穷举下一个数字的选择
        if (backtrack(nums, index + 1, bucket, target)) {
            return true;
        }
        // 撤销选择
        bucket[i] -= nums[index];
     
//剪枝 
if(bucket[i] == 0) break;

    }

添加最后一个剪枝，就能不超时了

[Rayantenna]

如果nums[index]装入当前桶bucket[i]是失败的，那么继续尝试装入其它的桶也一定失败，所以不用继续试了

[chinajpr]

if(bucket[i] == 0) break;在撤回的位置。什么时候在撤回的位置同时bucket[i] == 0呢？就是在第一次往bucket[i]里面放数据的地方，能够撤回到这个地方，说明nums[index]放入bucket[i]是行不通的。那么这些桶都是一样的，放在bucket[i]里面行不通，放在其他桶里面就行得通了？也是行不通的，直接返回false.

[weixueman]

这个加了这个剪枝时间复杂度很低了啊，是O(k*n^2)吗

[Blank0120]

@zhao2019010704 想问一下是为什么啊 ?

[JamieLiu228]

@zhao2019010704 大佬能解释一下为啥最后一个桶如果等于0就跳出就等于剪枝呢，很巧妙

[diandengpao]

k == 0不是最后一个桶，k是从[k,..]开始计算的，所以1是最后一个桶。所以k==0时，代表前边已经装完[k,1]，也就是k个桶了。

[AllenZzz0]

if(bucket[i] == 0) break;这个剪枝我感觉像是int[] nums里面的某一个数循环了一圈都没有找到合适的数去配队凑成target，所以后面的都不用在看了，必定凑不成题目说的那种。
例：nums[0] = 7, target = 8,现在bucket[]里面只放了一个7，循环了一遍nums数组，发现找不到1，然后撤销选择bucket[i] -= nums[index]; 这时bucket[i]=0，所以直接break。
不知道理解的对不对

[AllenZzz0]

// 用@zhao2019010704大佬的方式加工的
public boolean helper(int[] bucket, int target, int[] nums, int index) {
        // base case，index来记录当前循环到第几个数据了
        if(index == nums.length) {
            // nums[]遍历完了，这时候说明所有数都找到了桶，如果没找到的话会在bucket[i] == 0被剪掉
            return true;
        }
        // 穷举 nums[index] 可能装入的桶
        for(int i = 0; i < bucket.length; i++) {
            if(bucket[i] + nums[index] > target) {
                continue;
            }
            // 装进去
            bucket[i] += nums[index];
            if(help(bucket, target, nums, index + 1)) {
                return true;
            }
            // 到这里说明上面没有return,修建
            bucket[i] -= nums[index];
            // 这里可能index还没到nums.length，但是出现了无法凑成target的数，所以直接返回break，然后fasle就行
            if(bucket[i] == 0) {
                // nums[index]找不到可以凑成target的数
                break;
            }
        }
        return false;
    }

[Jun-Zhang-32108]

我的理解思路是这样的：

1. 桶与桶之间是没有差异的，如果一个数放入桶A中无法找到其他数使桶A的和为target，则该数放入桶B也不行；
2. 如果一个数不能放入某一个桶中去满足和为target的条件，则不能划分为k个和相等的子集；
3. 如果一个数放入bucket[i]，又回退撤回了，且此时bucket[i]为空，则说明回退到起点了，说明这个数放入后无论如何都无法满足这个bucket的和为target的情况（否则为什么要回退撤回呢），则说明不能划分为k个和相等的子集。

[H-YaoDong]

boolean backtrack(int k, int bucket, 
	...
    /*
    if (k == 0) {
        return true;
    }*/
    /*用 k==1 来进行判断也是可以的，因为除了最后一个桶没有确定外，其他的桶都确定了其中的数字（桶中数字的和等于target），那么还没有被添加到桶中的数字必定会被添加到最后一个桶中，因此就不需要在额外判断
    */
    if(k==1)	return true;
	...

[YiRu-hub]

根据大佬们的剪枝和解释，再+一个剪枝
if(nums[0]>target) return false;
对于已经降序排序的数组，如果第一个数字就比目标数字大，那肯定是凑不齐了，举例nums=[7,6,4,1],k=3,target=sum/k=6.

[wangnan0916]

位运算不熟练的同学，可以用bitset 嘿嘿

class Solution {
public:
    bool canPartitionKSubsets(vector<int> &nums, int k) {
        typedef bitset<20> bs20;
        if (k > nums.size())return false;
        int sum = 0;
        for (int i: nums)sum += i;
        if (sum % k)return false;
        int target = sum / k;
        //最大的数比target大
        if(nums[0]>target)return false;
        unordered_set<bs20> memo;
        sort(nums.begin(), nums.end(), greater<int>());
        function<bool(int, int, bs20)> backtrack = [&](int at, int sum, bs20 used) {
            if (memo.count(used))return false;
            if (at == k) {
                return true;
            }
            if (sum == target) {
                return backtrack(at + 1, 0, used);
            } else {
                for (int i = 0; i < nums.size(); i++) {
                    if (used[i])continue;
                    if (sum + nums[i] > target)continue;
                    sum += nums[i];
                    used[i] = 1;
                    if (backtrack(at, sum, used)) {
                        return true;
                    } else {
                        //记录失败情况
                        memo.insert(used);
                    }
                    sum -= nums[i];
                    used[i] = 0;
                    //没有能够凑成target
                    if(sum==0)break;
                }
            }
            return false;
        };
        return backtrack(0, 0, 0);
    }
};

[cmh1779]

if(bucket[i] == 0) break; 个人理解是：当前的桶经过上面的试探后无法满足条件，桶还是空的，所以后面的桶也不用试了，不可能满足条件，所以直接返回false。不知道这样理解对不对呢？

[tiangarin]

贴一个解法，增加两种剪枝，第二种剪枝不怎么用，只有在数组中具有大量和target相等的数时才有用。

class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        total_sum = sum(nums)
        if total_sum % k != 0:
            return False
        self.target = total_sum // k
        nums = sorted(nums, reverse=True)

        if nums[0] > self.target:
            return False

        # start, end = -1, -1
        # for i,v in enumerate(nums):
        #     if v == self.target:
        #         if start == -1:
        #             start = i
        #             end = i
        #         else:
        #             end = i
        #     elif v < self.target:
        #         break
        # if start != -1:
        #     nums = nums[:start]+nums[end+1:]
        #     k = k-(end-start+1)
        
        self.nums = nums
        self.k = k 
        self.used = 0
        self.mem = dict()  # 备忘录，避免不同子集的相同组合数（因为这题关注的每个子集组合数的总和，不需要关心子集的顺序）
        return self.DFS(0, 0, 0)
        
    def DFS(self, k, cur, start):
        if k == self.k:
            return True
        if self.target == cur:
            res = self.DFS(k+1, 0, 0)
            self.mem[self.used] = res
            return res
        if self.used in self.mem:
            return self.mem[self.used]
        for i in range(len(self.nums)):
            if cur + self.nums[i] > self.target:
                continue
            if ((self.used>>i) & 1) == 1:
                continue
            self.used |= 1<<i
            cur += self.nums[i]
            if self.DFS(k, cur, i+1):
                return True
            cur -= self.nums[i]
            self.used ^= 1<<i
        return False

[Hyuvo]

感觉这个medium好难啊，这么多层优化

[lambdaxing]

看了其他答案和评论，改了改东哥的第一种数字视角的解法，加了些注释进行解释：

class Solution {
public:

    bool res = false;
    
    void backtrack(vector<int>& nums, int index, vector<int>& buckets, int target) {
        // 已经得出答案，直接返回。
        if(res) return;
        
        if(index >= nums.size()) {
            // index 递归到 nums.size() 时，nums 中的每个元素都放入了某个桶，同时每个桶都满足其元素和 <= target，
            // 即 sum(buckets) = sum(nums)，相当于 k * target = k * buckets[i]，又 bucket[i] <= target,
            // 所以必须要是 bucket[i] = target，找到了一个组合满足要求。
            res = true;
            return;
        }

        for(int i = 0; i < buckets.size(); i++) {
            if(buckets[i] + nums[index] > target)
                continue;
            // 对于 nums[index]，bucket[i-1] 装入后没得到答案，bucket[i] 与 bucket[i-1] 相等，
            // 每个桶的和都要满足等于 target，这两个桶装入 nums[index] 的情况应该相同，即都是无法满足要求。
            if(i > 0 && buckets[i] == buckets[i-1])
                continue;
            buckets[i] += nums[index];
            backtrack(nums, index + 1, buckets, target);
            buckets[i] -= nums[index];
        }
    }

    bool canPartitionKSubsets(vector<int>& nums, int k) {
        sort(nums.rbegin(), nums.rend());
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if(sum % k != 0)
            return false;
        vector<int> buckets(k, 0);  // k 个桶，初始容量为 0
        backtrack(nums, 0, buckets, sum/k);
        return res;
    }
};

[llxblhyvia]

谢谢大佬！好牛！我终于明白这个为什么index>=nums.size()的时候可以直接return True了！

[znh0503]

一点看法：

• 视角问题
  1)以数字的视角入桶，由于1个数字只能进1个桶（一对一），此时做回溯的选择只需要在桶列表里面选择一个桶，逻辑简单。
  2)以桶的视角选择数字，由于1个桶可以拥有多个数字（一对多），此时做回溯的选择就不是在数字列表里面选一个数字了，而是需要选择多个数字直到桶满，再去第二个桶……，逻辑复杂。
• 优化
  1)排序让大数先选桶
  2)记录桶容量状态，一个数字进入相同容量状态的桶效果是一样的。

public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum=0;
        for (int i = 0; i < nums.length; i++) {
            sum+=nums[i];
        }
        if (sum%k!=0)return false;
        Arrays.sort(nums);
        //每个子集的和
        int targetSum=sum/k;
        //抽象桶
        int[] bucket=new int[k];
        Arrays.fill(bucket,targetSum);
//        for (int i = 0; i < bucket.length; i++) {
//            LinkedList<Integer> bucketList=new LinkedList<>();
//            bucketLists.add(bucketList);
//        }
        boolean result = dfs(nums, nums.length-1, bucket);
        return result;
    }

    //List<LinkedList<Integer>> bucketLists=new ArrayList<>();
    //元素是否可以放入桶
    public boolean dfs(int[] nums,int index,int[] bucket){
        //base case
        if (index<0){
            return true;
        }
        int cur = nums[index];
        //记录前面选过的桶的状态
        Set<Integer> memo=new HashSet<>();
        //选择桶
        for (int i=0;i<bucket.length;i++){
            //剪枝
            if (memo.contains(bucket[i])||bucket[i]-cur<0){
                continue;
            }
            //选择
            bucket[i]-=cur;
           // LinkedList<Integer> bucketList = bucketLists.get(i);
            //bucketList.push(cur);
            //下一个数
            if (dfs(nums,index-1,bucket)){
                return true;
            }
            //撤销选择
            bucket[i]+=cur;
           // bucketList.poll();
            //记录上次的入桶失败的桶状态
            memo.add(bucket[i]);
        }
        return false;
    }

[zdcat]

说一下自己看的时候遇到的问题，自己也是想了一会才发现的，以桶的视角去实现代码的时候之所以每次 for 都是从 start 开始的原因是，以桶的视角来选择数字，本质上来说就是一个数字的组合问题，组合的问题是不需要考虑排列的，所以自然不需要从使 i 每次从 0 开始，虽然从 0 开始也可以解决问题，但是在递归的时候会走出多余的很多的递归，提交的时候就会超时。
如果有错误望指正

[zdcat]

看这一篇文章的时候我还没有看这一篇的下一篇《回溯算法秒杀所有排列-组合-子集问题》，在排列组合这一篇文章里对于 for 从 start 开始有了更好的理解，只能说东哥太牛了

[aYuIsOK]

对东哥的以数组视角算法进行的优化

1. 既然是倒序, 可以直接在函数上进行优化, 从length-1开始递归
2. 剪枝优化: if(i > 0 && buckets[i] == buckets[i - 1]) continue; 如果当前桶与前一个桶一样说明都不满足, 可以直接剪枝
3. 主函数优化: 数组最大值max > target, 无法入桶, 直接返回false; target * k != sum , 说明target是违法值, 直接返回false

[aYuIsOK]

没仔细看, 已经用 sum % k 判断合法性了, 粗心了

[fonkie]

javascript版本

/** 
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var canPartitionKSubsets = function(nums, k) {
    /* 85ms, 42.1mb,  以数字的视角
    if(k > nums.length){ return false; }
    let sum = 0;
    nums.forEach((v) => {
        sum += v;
    });
    if(sum % k !== 0){ return false; }

    nums.sort((x, y) => y - x);

    const bucket =  new Array(k).fill(0);
    const target = sum / k;
    const backtrack = (index) => {
        if(index === nums.length){
            return true;
        }
        for(let i = 0; i < bucket.length; i++){
            if(bucket[i] + nums[index] > target){
                continue;
            }
            bucket[i] += nums[index];
            if(backtrack(index + 1)){
                return true;
            }
            bucket[i] -= nums[index];
            if(bucket[i] === 0){
                break;
            }
        }
        return false;
    }
    return backtrack(0);
    */

    //  3772ms, 42mb 以桶的视角
    if(k > nums.length){ return false; }
    let sum = 0;
    nums.forEach((v) => {
        sum += v;
    });
    if(sum % k !== 0){ return false; }

    nums.sort((x, y) => y - x);

    const target = sum / k;
    const used = new Array(nums.length).fill(false);
    const backtrack = (k, start, bucket) => {
        if(k === 0){ return true; }
        if(bucket === target){
            return backtrack(k - 1, 0, 0);
        }
        if(bucket > target){ 
            return false; 
        }

        for(let i = start; i < nums.length; i++){
            if(used[i] || nums[i] + bucket > target){
                continue;
            }
            used[i] = true;
            if(backtrack(k, i + 1, nums[i] + bucket)){
                return true;
            }
            used[i] = false;
        }
        return false;
    };
    return backtrack(k, 0, 0);

};

[marcmk6]

思路拆解写的太好了👍🏻
我自己的思路是先找到所有唯一的凑sum(nums) // k的组合，然后用全部数字扣除一组凑成组合的数字和k-1做递归，写了两个多小时😅，看完文章后发现属于文中描述的桶视角

[Rayantenna]

if(bucket[i] == 0) break; // 如果nums[index]装入当前桶bucket[i]是失败的，那么继续尝试装入其它的桶也一定失败，所以不用继续试了

[chen821240134]

class Solution {
public:
    vector<int> bucket;
    vector<bool> visited;
    bool backtrace(int k, vector<int>& nums, int target, int start){
        if(bucket.size() == k) return true;
        if(bucket[k]==target)
            return backtrace(k+1, nums, target, 0);
        for(int i=start; i<nums.size(); i++){ // i=start 是关键的一步
            if(visited[i]) continue;
            // int num = nums[i];
            if(bucket[k]+nums[i] > target) continue;
            visited[i] = true;
            bucket[k]+=nums[i];
            if(backtrace(k, nums, target,i+1)) return true;
            visited[i] = false;
            bucket[k]-=nums[i];
        }
        return false;
    }
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        bucket.resize(k,0);
        visited.resize(nums.size(),false);
        // sort(nums.begin(), nums.end(),greater<>());
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if(sum%k!=0) return false;
        int target = sum/k;
        // if(nums[0] > target) return false;
        return backtrace(0,nums,target,0);;
    }
};

哥几个，桶视角，我这个代码为啥后面几个测试点过不去啊？感觉和东哥的差不了多少啊。

[chen821240134]

贴错代码了

class Solution {
public:
    vector<int> bucket;
    vector<bool> visited;
    bool backtrace(int k, vector<int>& nums, int target, int start, int bucket_sum){
        if(0 == k) return true;
        if(bucket_sum == target)
            return backtrace(k-1, nums, target, 0, 0);
        for(int i=start; i<nums.size(); i++){ // i=start 是关键的一步
            if(visited[i]) continue;
            // int num = nums[i];
            if(bucket_sum + nums[i] > target) continue;
            visited[i] = true;
            bucket_sum+=nums[i];
            if(backtrace(k, nums, target, i+1, bucket_sum)) return true;
            visited[i] = false;
            bucket_sum-=nums[i];
        }
        return false;
    }
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        // bucket.resize(k,0);
        visited.resize(nums.size(),false);
        if(k>nums.size()) return false;
        // sort(nums.begin(), nums.end(),greater<>());
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if(sum%k!=0) return false;
        int target = sum/k;
        // if(nums[0] > target) return false;
        return backtrace(k,nums,target,0,0);
    }
};

[chen821240134]

运行能过，但是提交过不了，什么鬼

[bruceeewong]

看这题的解题真是神游，仔仔细细看了两遍才搞懂。2轮优化太厉害，尤其是位图的操作开眼界了，时间从11%->73%。

[gaosh96]

时间 3 ms 击败 75.16% 内存 39.4 MB 击败 44.49%

    public boolean canPartitionKSubsets(int[] nums, int k) {
        // k 前置的两个条件
        if (k > nums.length) return false;
        int sum = Arrays.stream(nums).sum();
        if (sum % k != 0) return false;

        int target = sum / k;
        // 划分为 k 个子集
        int[] bucket = new int[k];

        // 优化点1：数组倒序
        Arrays.sort(nums);
        // 双指针反转数组
        for (int i = 0, j = nums.length - 1; i < j; i++, j--) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }

        return backtrace(nums, 0, bucket, target);
    }

    private boolean backtrace(int[] nums, int index, int[] bucket, int target) {
        if (index == nums.length) {
            // 优化点2：这个地方可以不需要再每个都判断，所有球已经按要求放入每个桶，一定满足条件 target
            return true;
        }

        for (int i = 0; i < bucket.length; i++) {
            // 优化点3：类似组合可重不可复选问题的剪枝
            // 当桶的和相同时，选择当前桶和前面的桶结果是一样的
            if (i > 0 && bucket[i] == bucket[i - 1]) continue;

            // 剪枝
            if (bucket[i] + nums[index] > target) {
                continue;
            }

            bucket[i] += nums[index];
            if (backtrace(nums, index + 1, bucket, target)) return true;
            bucket[i] -= nums[index];
        }

        return false;
    }

[zhandand]

为什么正向遍历，从0号遍历到k号桶时return true却会报错呢

[diandengpao]

我写的也是正向遍历，可以通过

[ngokchaoho]

通俗来说，我们应该尽量「少量多次」，就是说宁可多做几次选择（乘法关系），也不要给太大的选择空间（指数关系）；做 n 次「k 选一」仅重复一次（O(k^n)），比 n 次「二选一」重复 k 次（O(k*2^n)）效率低很多。

我有一點疑惑，在不考慮其它優化的情況下，只考慮桶視角/數字視角，兩種方式不應該是一樣的時間嗎？雖然從上界BIG O 分析看來，桶數角比較小，但如果都需要遍歷所有情況，實際需時不應該是一樣的嗎？

覺得桶視角的最大優勢，在於桶是同質的，因此可以減少很多搜㝷空間（但這點是沒有在BIG O分析下是看不出來的）。

[ngokchaoho]

typo: 但這點在BIG O分析下是看不出來的

[diandengpao]

我觉得主要在于剪枝，数字的角度必须要遍历完才能判断和是否相等，而桶的角度则可以通过判断一个桶的桶和是否超过target而省略。

[fangyuan99]

对位运算不熟的朋友可以用Arrays.hashCode

使用boolean[] used(100多ms)或者byte[] used(60ms和位运算的50ms差不多了)

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        // 排除一些基本情况
        if (k > nums.length) return false;
        int sum = 0;
        for (int v : nums) sum += v;
        if (sum % k != 0) return false;

        int target = sum / k;
        // k 号桶初始什么都没装，从 nums[0] 开始做选择
        boolean[] used = new boolean[nums.length];
        return backtrack(k, 0, nums, 0, used, target);
    }
    HashMap<Integer, Boolean> memo = new HashMap<>();

    boolean backtrack(int k, int bucket, int[] nums, int start, boolean[] used, int target) {
        // base case
        if (k == 0) {
            return true;
        }
        // 将 used 的状态转化成hashCode
        // 便于存入 HashMap
        int state = Arrays.hashCode(used);

        if (bucket == target) {
            // 装满了当前桶，递归穷举下一个桶的选择
            boolean res = backtrack(k - 1, 0, nums, 0, used, target);
            // 将当前状态和结果存入备忘录
            memo.put(state, res);
            return res;
        }

        if (memo.containsKey(state)) {
            // 如果当前状态曾今计算过，就直接返回，不要再递归穷举了
            return memo.get(state);
        }

        // 从 start 开始向后探查有效的 nums[i] 装入当前桶
        for (int i = start; i < nums.length; 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;
    }
}

[shiboys]

把回溯和递归重新外出了新高度！！！赞一个