Code More Create

Appearance

Return to top
On this page

集合划分问题

回溯算法的关键在哪里？

关键是要知道怎么「做选择」，这样才能利用递归函数进行穷举。

将 n 个数字分配到 k 个桶里，我们可以有两种视角：

视角一，如果我们切换到这 n 个数字的视角，每个数字都要选择进入到 k 个桶中的某一个。

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

以数字的视角

以桶的视角

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

class Solution {
        public boolean canPartitionKSubsets(int[] nums, int k) {
        //corner case
        if(k > nums.length) return false;

        int sum = 0;
        for(int num : nums) {
            sum += num;
        }
        if(sum % k != 0) return false;

        //k个桶，值为桶内的元素和
        int[] bucket = new int[k];
        //判断每个元素是否已经放入某桶中
        boolean[] used = new boolean[nums.length];
        //每个桶内应该放的元素之和
        int target = sum / k;
        //当前未满足的还有k个桶；当前第k个桶内已有的元素和为0；nums数组；选择列表的起点元素；used数组；每个桶内应该放的元素之和
        return dfs(k, 0, nums, 0, used, target);
    }

    public boolean dfs(int k, int curSum, int[] nums, int start, boolean[] used, int target) {
        //所有桶都已达到目标元素和
        if(k == 0) return true;
        
        //当前桶内的元素和已达到target
        //当装满一个桶后，还需要装下一个桶
        if(curSum == target) {
            return dfs(k - 1, 0, nums, 0, used, target);
        }

        for(int i = start; i < nums.length; i++) {
            if(used[i]) {
                continue;
            }
            if(curSum + nums[i] > target) {
                continue;
            }

            //作出选择
            used[i] = true;
            curSum += nums[i];
            
            if(dfs(k, curSum, nums, i + 1, used, target)) {
                return true;
            }
            
            //撤销选择
            used[i] = false;
            curSum -= nums[i];
        }

        //穷举了所有未放入桶内的数字，都没装满桶
        return false;
    }
}