Java教程

回溯算法-子集组合排列

本文主要是介绍回溯算法-子集组合排列,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

本文分享一些自己在刷回溯算法-子集组合排列时总结的套路。

一、回溯算法和二叉树的联系

  1. 回溯算法本质上是决策树的选择和撤销过程,所以也属于二叉树。
  2. 回溯算法框架中会出现for循环中嵌套递归,for是广度搜索,递归是深度搜索;在二叉树中,经常会有traverse(root.left)和traverse(root.right),其实这里是将for循环给具体写成了两个递归函数进行广度搜索,然后递归函数进行深度搜索。
  3. 回溯算法放到二叉树中说,相当于在前序位置和后序位置进行操作。

二、回溯算法分类

分类规则:原数组中的元素是否重复 | 数组中的元素是否可以复用

1. 元素无重复并且不可复用

相关题目参考LeetCode78、77、46:

2. 元素有重复并且不可复用

相关题目参考LeetCode90、40、47:

3. 元素无重复并且可以复用

相关题目参考LeetCode39:

三、子集组合排列模块化

本节将子集组合排列模块化,在以后做题时根据题目要求选取模块组装即可,需要做过一些子集组合排列相关回溯题目,对其有一定理解。

1. 回溯函数基本框架

List<List<Integer>> res = new LinkedList<>();
LinkedList<Integer> track = new LinkedList<>();
void backtrack(arg...) {
    //根据条件将路径加入结果集
    if(条件判断) {
        res.add(new LinkedList<>(track));
        return;
    }
    for(循环条件) {
        track.add(数值);
        backtrack(arg...);
        track.removeLast();
    }
}

2. 模块1:if(条件判断)

子集:求全部的子集,不需要条件判断
组合:需要条件判断,一般判断是track.size() == k即符合组合大小K的路径才会添加到结果集
排列:需要条件判断,一般判断是track.size() == nums.length即将数组中的元素全部添加的路径才会添加到结果集
分析:组合和排列的判断条件本质上是一样的,都是取某一层的结果。

3. 模块2:for(循环条件)

子集:for(int i=start; i<nums.length; i++) + backtrack(nums,i+1)
组合:for(int i=start; i<nums.length; i++)/for(int i=start; i<nums.length-(k-track.size())+1; i++) + backtrack(nums,i+1)
排列:for(int i=0; i<nums.length; i++) + if(used[i]) {continue;}
分析:for循环的功能:1.遍历数组 2.在子集和组合问题和backtrack(nums,i+1)配合防止元素被重复使用。 3.在排列问题中和if(used[i]) {continue;}配合防止重复选择

4. 模块3:arg...参数列表

子集:(1)表征数组:int[] nums或者int n (2)表征start:int start
组合:(1)表征数组:int[] nums或者int n (2)表征start:int start (3)表征取第几层集合([]集合是第一层):int k
排列:(1)表征数组:int[] nums

5. 模块4:假设元素可以重复

子集:(1)Arrays.sort(nums):排序,让相同的元素靠在一起 (2)在for循环中假如if(i>start && nums[i] == nums[i-1]) {continue;}:i>start使nums[i-1]存在;nums[i] == nums[i-1] 跳过相同的元素
组合:同子集
排列:跟子集略有不同:if(i>start && nums[i] == nums[i-1] && !used[i-1]) {continue;}:新增!used[i-1]是为了固定元素的相对顺序,防止出现重复结果

6. 模块5:假设元素可以复用

此模块与模块2+4相反,模块2的条件都是为了元素不被复用
子集:backtrack(nums,i+1)改为backtrack(nums,i),且不加模块4的条件
组合:同子集
排列:去掉used剪枝逻辑

7. 总结:

子集和组合可以归为一类,backtrack(nums,i+1)是防止同一元素被多次使用,if(i>start && nums[i] == nums[i-1]) 是防止出现重复的结果。
排序单独一类:if(used[i]) {continue;}是防止同一元素被多次使用,!used[i-1]是防止出现重复结果。
排序实则是对子集和组合结果的进一步划分,所以比子集组合的条件更加苛刻。

题目链接:

leetcode-78:子集
leetcode-77:组合
leetcode-46:全排列
leetcode-90:子集II
leetcode-40:组合总和II
leetcode-47:全排列II
leetcode-39:组合总和

声明:本文章参考了东哥的算法小抄,随笔中有很多地方都没有都没有具体解释,主要是作为自己的回顾随笔,如果有不清楚的,可以先看东哥的算法小抄。

这篇关于回溯算法-子集组合排列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!