关于后端:经典回溯算法集合划分问题

39次阅读

共计 8571 个字符,预计需要花费 22 分钟才能阅读完成。

读完本文,你不仅学会了算法套路,还能够顺便去 LeetCode 上拿下如下题目:

698. 划分为 k 个相等的子集(中等)

———–

之前说过回溯算法是口试中最好用的算法,只有你没什么思路,就用回溯算法暴力求解,即使不能通过所有测试用例,多少能过一点。

回溯算法的技巧也不难,前文 回溯算法框架套路 说过,回溯算法就是穷举一棵决策树的过程,只有在递归之前「做抉择」,在递归之后「撤销抉择」就行了。

然而,就算暴力穷举,不同的思路也有优劣之分

本文就来看一道十分经典的回溯算法问题,力扣第 698 题「划分为 k 个相等的子集」。这道题能够帮你更深刻理解回溯算法的思维,得心应手地写出回溯函数。

题目非常简单:

给你输出一个数组 nums 和一个正整数 k,请你判断 nums 是否可能被平分为元素和雷同的 k 个子集。

函数签名如下:

boolean canPartitionKSubsets(int[] nums, int k);

咱们之前 背包问题之子集划分 写过一次子集划分问题,不过那道题只须要咱们把汇合划分成两个相等的汇合,能够转化成背包问题用动静布局技巧解决。

然而如果划分成多个相等的汇合,解法个别只能通过暴力穷举,工夫复杂度爆表,是练习回溯算法和递归思维的好机会。

一、思路剖析

首先,咱们回顾一下以前学过的排列组合常识:

1、P(n, k)(也有很多书写成 A(n, k))示意从 n 个不同元素中拿出 k 个元素的排列(Permutation/Arrangement);C(n, k) 示意从 n 个不同元素中拿出 k 个元素的组合(Combination)总数。

2、「排列」和「组合」的次要区别在于是否思考程序的差别。

3、排列、组合总数的计算公式:

好,当初我问一个问题,这个排列公式 P(n, k) 是如何推导进去的?为了搞清楚这个问题,我须要讲一点组合数学的常识。

排列组合问题的各种变体都能够形象成「球盒模型」,P(n, k) 就能够形象成上面这个场景:

即,将 n 个标记了不同序号的球(标号为了体现程序的差别),放入 k 个标记了不同序号的盒子中(其中 n >= k,每个盒子最终都装有恰好一个球),共有 P(n, k) 种不同的办法。

当初你来,往盒子里放球,你怎么放?其实有两种视角。

首先,你能够站在盒子的视角 ,每个盒子必然要抉择一个球。

这样,第一个盒子能够抉择 n 个球中的任意一个,而后你须要让剩下 k - 1 个盒子在 n - 1 个球中抉择:

另外,你也能够站在球的视角 ,因为并不是每个球都会被装进盒子,所以球的视角分两种状况:

1、第一个球能够不装进任何一个盒子,这样的话你就须要将剩下 n - 1 个球放入 k 个盒子。

2、第一个球能够装进 k 个盒子中的任意一个,这样的话你就须要将剩下 n - 1 个球放入 k - 1 个盒子。

联合上述两种状况,能够失去:

你看,两种视角失去两个不同的递归式,但这两个递归式解开的后果都是咱们熟知的阶乘模式:

至于如何解递归式,波及数学的内容比拟多,这里就不做深入探讨了,有趣味的读者能够自行学习组合数学相干常识。

回到正题,这道算法题让咱们求子集划分,子集问题和排列组合问题有所区别,但咱们能够借鉴「球盒模型」的形象,用两种不同的视角来解决这道子集划分问题。

把装有 n 个数字的数组 nums 分成 k 个和雷同的汇合,你能够设想将 n 个数字调配到 k 个「桶」里,最初这 k 个「桶」里的数字之和要雷同。

前文 回溯算法框架套路 说过,回溯算法的要害在哪里?

要害是要晓得怎么「做抉择」,这样能力利用递归函数进行穷举。

那么模拟排列公式的推导思路,将 n 个数字调配到 k 个桶里,咱们也能够有两种视角:

视角一,如果咱们切换到这 n 个数字的视角,每个数字都要抉择进入到 k 个桶中的某一个

视角二,如果咱们切换到这 k 个桶的视角,对于每个桶,都要遍历 nums 中的 n 个数字,而后抉择是否将以后遍历到的数字装进本人这个桶里

你可能问,这两种视角有什么不同?

用不同的视角进行穷举,尽管后果雷同,然而解法代码的逻辑齐全不同,进而算法的效率也会不同;比照不同的穷举视角,能够帮你更粗浅地了解回溯算法,咱们缓缓道来

二、以数字的视角

用 for 循环迭代遍历 nums 数组大家必定都会:

for (int index = 0; index < nums.length; index++) {System.out.println(nums[index]);
}

递归遍历数组你会不会?其实也很简略:

void traverse(int[] nums, int index) {if (index == nums.length) {return;}
    System.out.println(nums[index]);
    traverse(nums, index + 1);
}

只有调用 traverse(nums, 0),和 for 循环的成果是齐全一样的。

那么回到这道题,以数字的视角,抉择 k 个桶,用 for 循环写进去是上面这样:

// k 个桶(汇合),记录每个桶装的数字之和
int[] bucket = new int[k];

// 穷举 nums 中的每个数字
for (int index = 0; index < nums.length; index++) {
    // 穷举每个桶
    for (int i = 0; i < k; i++) {// nums[index] 抉择是否要进入第 i 个桶
        // ...
    }
}

如果改成递归的模式,就是上面这段代码逻辑:

// k 个桶(汇合),记录每个桶装的数字之和
int[] bucket = new int[k];

// 穷举 nums 中的每个数字
void backtrack(int[] nums, int index) {
    // base case
    if (index == nums.length) {return;}
    // 穷举每个桶
    for (int i = 0; i < bucket.length; i++) {
        // 抉择装进第 i 个桶
        bucket[i] += nums[index];
        // 递归穷举下一个数字的抉择
        backtrack(nums, index + 1);
        // 撤销抉择
        bucket[i] -= nums[index];
    }
}

尽管上述代码仅仅是穷举逻辑,还不能解决咱们的问题,然而只有略加欠缺即可:

// 主函数
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;

    // k 个桶(汇合),记录每个桶装的数字之和
    int[] bucket = new int[k];
    // 实践上每个桶(汇合)中数字的和
    int target = sum / k;
    // 穷举,看看 nums 是否能划分成 k 个和为 target 的子集
    return backtrack(nums, 0, bucket, target);
}

// 递归穷举 nums 中的每个数字
boolean backtrack(int[] nums, int index, int[] bucket, int target) {if (index == nums.length) {
        // 查看所有桶的数字之和是否都是 target
        for (int i = 0; i < bucket.length; i++) {if (bucket[i] != target) {return false;}
        }
        // nums 胜利平分成 k 个子集
        return true;
    }
    
    // 穷举 nums[index] 可能装入的桶
    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];
    }

    // nums[index] 装入哪个桶都不行
    return false;
}

有之前的铺垫,置信这段代码是比拟容易了解的。这个解法尽管可能通过,然而耗时比拟多,其实咱们能够再做一个优化。

次要看 backtrack 函数的递归局部:

for (int i = 0; i < bucket.length; i++) {
    // 剪枝
    if (bucket[i] + nums[index] > target) {continue;}

    if (backtrack(nums, index + 1, bucket, target)) {return true;}
}

如果咱们让尽可能多的状况命中剪枝的那个 if 分支,就能够缩小递归调用的次数,肯定水平上缩小工夫复杂度

如何尽可能多的命中这个 if 分支呢?要晓得咱们的 index 参数是从 0 开始递增的,也就是递归地从 0 开始遍历 nums 数组。

如果咱们提前对 nums 数组排序,把大的数字排在后面,那么大的数字会先被调配到 bucket 中,对于之后的数字,bucket[i] + nums[index] 会更大,更容易触发剪枝的 if 条件。

所以能够在之前的代码中再增加一些代码:

boolean canPartitionKSubsets(int[] nums, int k) {
    // 其余代码不变
    // ...
    /* 降序排序 nums 数组 */
    Arrays.sort(nums);
    for (i = 0, j = nums.length - 1; i < j; i++, j--) {// 替换 nums[i] 和 nums[j]
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    /*******************/
    return backtrack(nums, 0, bucket, target);
}

因为 Java 的语言个性,这段代码通过先升序排序再反转,达到降序排列的目标。

三、以桶的视角

文章结尾说了, 以桶的视角进行穷举,每个桶须要遍历 nums 中的所有数字,决定是否把以后数字装进桶中;当装满一个桶之后,还要装下一个桶,直到所有桶都装满为止

这个思路能够用上面这段代码示意进去:

// 装满所有桶为止
while (k > 0) {
    // 记录以后桶中的数字之和
    int bucket = 0;
    for (int i = 0; i < nums.length; i++) {// 决定是否将 nums[i] 放入以后桶中
        bucket += nums[i] or 0;
        if (bucket == target) {
            // 装满了一个桶,装下一个桶
            k--;
            break;
        }
    }
}

那么咱们也能够把这个 while 循环改写成递归函数,不过比方才稍微简单一些,首先写一个 backtrack 递归函数进去:

boolean backtrack(int k, int bucket, 
    int[] nums, int start, boolean[] used, int target);

不要被这么多参数吓到,我会一个个解释这些参数。 如果你可能透彻了解本文,也能得心应手地写出这样的回溯函数

这个 backtrack 函数的参数能够这样解释:

当初 k 号桶正在思考是否应该把 nums[start] 这个元素装进来;目前 k 号桶外面曾经装的数字之和为 bucketused 标记某一个元素是否曾经被装到桶中;target 是每个桶须要达成的指标和。

依据这个函数定义,能够这样调用 backtrack 函数:

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;
    
    boolean[] used = new boolean[nums.length];
    int target = sum / k;
    // k 号桶初始什么都没装,从 nums[0] 开始做抉择
    return backtrack(k, 0, nums, 0, used, target);
}

实现 backtrack 函数的逻辑之前,再反复一遍,从桶的视角:

1、须要遍历 nums 中所有数字,决定哪些数字须要装到以后桶中。

2、如果以后桶装满了(桶内数字和达到 target),则让下一个桶开始执行第 1 步。

上面的代码就实现了这个逻辑:

boolean backtrack(int k, int bucket, 
    int[] nums, int start, boolean[] used, int target) {
    // base case
    if (k == 0) {
        // 所有桶都被装满了,而且 nums 肯定全副用完了
        // 因为 target == sum / k
        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.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;
}

这段代码是能够得出正确答案的,然而效率很低,咱们能够思考一下是否还有优化的空间

首先,在这个解法中每个桶都能够认为是没有差别的,然而咱们的回溯算法却会对它们区别对待,这里就会呈现反复计算的状况。

什么意思呢?咱们的回溯算法,说到底就是穷举所有可能的组合,而后看是否能找出和为 targetk 个桶(子集)。

那么,比方上面这种状况,target = 5,算法会在第一个桶外面装 1, 4

当初第一个桶装满了,就开始装第二个桶,算法会装入 2, 3

而后以此类推,对前面的元素进行穷举,凑出若干个和为 5 的桶(子集)。

但问题是,如果最初发现无奈凑出和为 targetk 个子集,算法会怎么做?

回溯算法会回溯到第一个桶,从新开始穷举,当初它晓得第一个桶里装 1, 4 是不可行的,它会尝试把 2, 3 装到第一个桶里:

当初第一个桶装满了,就开始装第二个桶,算法会装入 1, 4

好,到这里你应该看进去问题了,这种状况其实和之前的那种状况是一样的。也就是说,到这里你其实曾经晓得不须要再穷举了,必然凑不出来和为 targetk 个子集。

但咱们的算法还是会傻乎乎地持续穷举,因为在她看来,第一个桶和第二个桶外面装的元素不一样,那这就是两种不一样的状况呀。

那么咱们怎么让算法的智商进步,辨认出这种状况,防止冗余计算呢?

你留神这两种状况的 used 数组必定长得一样,所以 used 数组能够认为是回溯过程中的「状态」。

所以,咱们能够用一个 memo 备忘录,在装满一个桶时记录以后 used 的状态,如果以后 used 的状态是已经呈现过的,那就不必再持续穷举,从而起到剪枝防止冗余计算的作用

有读者必定会问,used 是一个布尔数组,怎么作为键进行存储呢?这其实是小问题,比方咱们能够把数组转化成字符串,这样就能够作为哈希表的键进行存储了。

看下代码实现,只有略微改一下 backtrack 函数即可:

// 备忘录,存储 used 数组的状态
HashMap<String, 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 的状态转化成形如 [true, false, ...] 的字符串
    // 便于存入 HashMap
    String state = Arrays.toString(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);
    }

    // 其余逻辑不变...
}

这样提交解法,发现执行效率仍然比拟低,这次不是因为算法逻辑上的冗余计算,而是代码实现上的问题。

因为每次递归都要把 used 数组转化成字符串,这对于编程语言来说也是一个不小的耗费,所以咱们还能够进一步优化

留神题目给的数据规模 nums.length <= 16,也就是说 used 数组最多也不会超过 16,那么咱们齐全能够用「位图」的技巧,用一个 int 类型的 used 变量来代替 used 数组。

具体来说,咱们能够用整数 used 的第 i 位((used >> i) & 1)的 1/0 来示意 used[i] 的 true/false。

这样一来,不仅节约了空间,而且整数 used 也能够间接作为键存入 HashMap,省去数组转字符串的耗费。

看下最终的解法代码:

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 used = 0; // 应用位图技巧
    int target = sum / k;
    // k 号桶初始什么都没装,从 nums[0] 开始做抉择
    return backtrack(k, 0, nums, 0, used, target);
}

HashMap<Integer, Boolean> memo = new HashMap<>();

boolean backtrack(int k, int bucket,
                  int[] nums, int start, int used, int target) {        
    // base case
    if (k == 0) {
        // 所有桶都被装满了,而且 nums 肯定全副用完了
        return true;
    }
    if (bucket == target) {
        // 装满了以后桶,递归穷举下一个桶的抉择
        // 让下一个桶从 nums[0] 开始选数字
        boolean res = backtrack(k - 1, 0, nums, 0, used, target);
        // 缓存后果
        memo.put(used, res);
        return res;
    }
    
    if (memo.containsKey(used)) {
        // 防止冗余计算
        return memo.get(used);
    }

    for (int i = start; i < nums.length; i++) {
        // 剪枝
        if (((used >> i) & 1) == 1) { // 判断第 i 位是否是 1
            // nums[i] 曾经被装入别的桶中
            continue;
        }
        if (nums[i] + bucket > target) {continue;}
        // 做抉择
        used |= 1 << i; // 将第 i 地位为 1
        bucket += nums[i];
        // 递归穷举下一个数字是否装入以后桶
        if (backtrack(k, bucket, nums, i + 1, used, target)) {return true;}
        // 撤销抉择
        used ^= 1 << i; // 应用异或运算将第 i 位复原 0
        bucket -= nums[i];
    }

    return false;
}

至此,这道题的第二种思路也实现了。

四、最初总结

本文写的这两种思路都能够算出正确答案,不过第一种解法即使通过了排序优化,也显著比第二种解法慢很多,这是为什么呢?

咱们来剖析一下这两个算法的工夫复杂度,假如 nums 中的元素个数为 n

先说第一个解法,也就是从数字的角度进行穷举,n 个数字,每个数字有 k 个桶可供选择,所以组合出的后果个数为 k^n,工夫复杂度也就是 O(k^n)

第二个解法,每个桶要遍历 n 个数字,对每个数字有「装入」或「不装入」两种抉择,所以组合的后果有 2^n 种;而咱们有 k 个桶,所以总的工夫复杂度为 O(k*2^n)

当然,这是对最坏复杂度上界的粗略估算,理论的复杂度必定要好很多,毕竟咱们增加了这么多剪枝逻辑 。不过,从复杂度的上界曾经能够看出第一种思路要慢很多了。

所以,谁说回溯算法没有技巧性的?尽管回溯算法就是暴力穷举,但穷举也分聪慧的穷举形式和低效的穷举形式,要害看你以谁的「视角」进行穷举。

艰深来说,咱们应该尽量「少量多次」,就是说宁肯多做几次抉择,也不要给太大的抉择空间;宁肯「二选一」选 k 次,也不要「k 选一」选一次。

好了,这道题咱们从两种视角进行穷举,尽管代码量看起来多,但外围逻辑都是相似的,置信你通过本文可能更粗浅地了解回溯算法。

_____________

点击我的头像 查看更多优质算法文章,手把手带你刷力扣,致力于把算法讲清楚!我的 算法教程 曾经取得 100k star,欢送点赞!

正文完
 0