递归回溯实战+思想

目录

排列（提供元素无重复，并且不可以重复选择）

排列（提供的元素重复了，但是同个位置的元素不能复选）

组合（提供的元素没有重复，并且可以重复选择相同位置元素）

子集（提供的元素没有重复，且同位置元素只能选择一次）

组合（提供元素不重复，且同位置不能重复选）

---

 

排列（提供元素无重复，并且不可以重复选择）

思路：1.根据题意找到base case——>2.然后遍历提供的数据节点，（不可重复选择同一数据节点，并且提供的数据节点都没有重复）——>3.我们利用boolean数据进行判断，当前数据节点是否选择，如果选择过直接continue——>4.没有选择过进行选择逻辑并且修改状态——>5.进入递归函数——>6.回溯，撤销逻辑选择

 模板：

/* 组合/子集问题回溯算法框架 */
void backtrack(int[] nums, int start) {
    // 回溯算法标准框架
    for (int i = start; i < nums.length; i++) {
        // 做选择
        track.addLast(nums[i]);
        // 注意参数
        backtrack(nums, i + 1);
        // 撤销选择
        track.removeLast();
    }
}
 
/* 排列问题回溯算法框架 */
void backtrack(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        // 剪枝逻辑
        if (used[i]) {
            continue;
        }
        // 做选择
        used[i] = true;
        track.addLast(nums[i]);
 
        backtrack(nums);
        // 撤销选择
        track.removeLast();
        used[i] = false;
    }
}

例题：

46. 全排列 - 力扣（LeetCode）

 //1.结果集
    List>res=new LinkedList<>();
    public List> permute(int[] nums) {
        //1.记录一条路径
        LinkedListtrack = new LinkedList<>();
        //2.记录每个元素状态
        boolean[] used=new boolean[nums.length];
        backtrack(nums,track,used);
        return res; 
    }
    void backtrack(int[]nums,LinkedListtrack,boolean[]used){
       //1.结束条件
       if(track.size()==nums.length){
           res.add(new LinkedList(track));
           return;
       }
       //2.遍历每个元素
       for(int i=0;i
         //2.1排除不合法的选择
         if(used[i]){
             continue;
         }
         //2.2对当前元素做选择
         track.add(nums[i]);
         used[i]=true;
         backtrack(nums,track,used);
         //2.3进行回溯
         track.removeLast();
         used[i]=false;
 
       }
 
    }

排列（提供的元素重复了，但是同个位置的元素不能复选）

不同之处：和上述思路差不多，加了一个剪枝操作，因为提供的元素有重复（比如：【1，2，2】），所以我们需要固定重复元素的位置，防止出现重复结果

打个比方，就以 nums = [1,2,2] 为例，为了区别两个 2 是不同元素，后面我们写作 nums = [1,2,2']

——>显然，两条值相同的相邻树枝会产生重复

 剪枝：需要先进行排序，让相同的元素靠在一起，如果发现 nums[i] == nums[i-1]&&used[i-1] (排列情况)

比如输入 nums = [1,2,2',2'']，2' 只有在 2 已经被使用的情况下才会被选择，同理，2'' 只有在 2' 已经被使用的情况下才会被选择，这就保证了相同元素在排列中的相对位置保证固定

if (i > 0 && nums[i] == nums[i - 1] && used[i-1]) continue;

 模板：

Arrays.sort(nums);
/* 组合/子集问题回溯算法框架 */
void backtrack(int[] nums, int start) {
    // 回溯算法标准框架
    for (int i = start; i < nums.length; i++) {
        // 剪枝逻辑，跳过值相同的相邻树枝
        if (i > start && nums[i] == nums[i - 1]) {
            continue;
        }
        // 做选择
        track.addLast(nums[i]);
        // 注意参数
        backtrack(nums, i + 1);
        // 撤销选择
        track.removeLast();
    }
}
 
 
Arrays.sort(nums);
/* 排列问题回溯算法框架 */
void backtrack(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        // 剪枝逻辑
        if (used[i]) {
            continue;
        }
        // 剪枝逻辑，固定相同的元素在排列中的相对位置
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
            continue;
        }
        // 做选择
        used[i] = true;
        track.addLast(nums[i]);
 
        backtrack(nums);
        // 撤销选择
        track.removeLast();
        used[i] = false;
    }
}

例题：

47. 全排列 II - 力扣（LeetCode）

class Solution {
    List> perResult = new LinkedList<>();
    LinkedList perTrack = new LinkedList<>();
    boolean[] used;
 
    public List> permuteUnique(int[] nums) {
        //1.先排序
        Arrays.sort(nums);
        used = new boolean[nums.length];
        //2.递归函数
        permuteUniqueHelper(nums);
        return perResult;
    }
 
    void permuteUniqueHelper(int[] nums) {
        //1.base:子路径的结束条件
        if (perTrack.size() == nums.length) {
            perResult.add(new LinkedList<>(perTrack));
            return;
        }
        //2.遍历nums所有数据
        for (int i = 0; i < nums.length; i++) {
            //2.1判断当前节点有没有使用过——>使用过就不能再次出现
            if (used[i]) continue;
            //2.2剪枝逻辑，固定排序位置
            if (i > 0 && nums[i] == nums[i - 1] && used[i-1]) continue;
            //2.3添加当前节点进子序列
            perTrack.add(nums[i]);
            used[i]=true;
            permuteUniqueHelper(nums);
            //2.4回溯
            perTrack.removeLast();
            used[i]=false;
        }
 
    }
 
}

组合（提供的元素没有重复，并且可以重复选择相同位置元素）

一般作用于求和类组合题目上，像这种提供元素不重复（重复元素，要考虑去重->剪枝即可），可以重新选择（删除去重逻辑->start不+1）

39. 组合总和 - 力扣（LeetCode）

class Solution {
    List> res = new LinkedList<>();
// 记录回溯的路径
LinkedList track = new LinkedList<>();
// 记录 track 中的路径和
int trackSum = 0;
 
public List> combinationSum(int[] candidates, int target) {
    if (candidates.length == 0) {
        return res;
    }
    backtrack(candidates, 0, target);
    return res;
}
 
// 回溯算法主函数
void backtrack(int[] nums, int start, int target) {
    // base case，找到目标和，记录结果
    if (trackSum == target) {
        res.add(new LinkedList<>(track));
        return;
    }
    // base case，超过目标和，停止向下遍历
    if (trackSum > target) {
        return;
    }
 
    // 回溯算法标准框架
    for (int i = start; i < nums.length; i++) {
        // 选择 nums[i]
        trackSum += nums[i];
        track.add(nums[i]);
        // 递归遍历下一层回溯树
        // 同一元素可重复使用，注意参数
        backtrack(nums, i, target);
        // 撤销选择 nums[i]
        trackSum -= nums[i];
        track.removeLast();
    }
}
 
}

子集（提供的元素没有重复，且同位置元素只能选择一次）

思路：只能选择一次，每次进入递归的时候，利用一个变量+1（start+1）防止重复踩到相同位置元素——>1.因为是组合类题目，允许空集，所以前序位置直接结果集加一个子序列——>2.每次添加一个元素进入递归函数后——>结果集都会重新加一个子序列（也是通过start控制相同位置不重复访问的，利用track子序列添加元素，然后递归后慢慢撤销回溯，但是像我们以下的图，到i=2他就进不了1这个位置了）

模板：

List> res = new LinkedList<>();
// 记录回溯算法的递归路径
LinkedList track = new LinkedList<>();
 
// 主函数
public List> subsets(int[] nums) {
    backtrack(nums, 0);
    return res;
}
 
// 回溯算法核心函数，遍历子集问题的回溯树
void backtrack(int[] nums, int start) {
 
    // 前序位置，每个节点的值都是一个子集
    res.add(new LinkedList<>(track));
    
    // 回溯算法标准框架
    for (int i = start; i < nums.length; i++) {
        // 做选择
        track.addLast(nums[i]);
        // 通过 start 参数控制树枝的遍历，避免产生重复的子集
        backtrack(nums, i + 1);
        // 撤销选择
        track.removeLast();
    }
}

 例题：

78. 子集 - 力扣（LeetCode）

class Solution {
    //1.结果集
    List> result=new LinkedList<>();
    public List> subsets(int[] nums) {
       //2.单节点路径
       LinkedList track=new LinkedList<>();
       //3.递归函数
       back(nums,0,track);
       return result;
    }
 
    void back(int[]nums,int start,LinkedListtrack){
       //1.首先添加一个空集合,对于后面就是添加有数据的节点
       result.add(new LinkedList<>(track));
       //2.回溯得到组合框架
       for(int i=start;i
           //2.1添加节点
           track.addLast(nums[i]);
           //2.2进行递归
           back(nums,i+1,track);
           //2.3回溯
           track.removeLast();
       }
 
    }
}

组合（提供元素不重复，且同位置不能重复选）

思路：跟子集一样，

你比如说，让你在 nums = [1,2,3] 中拿 2 个元素形成所有的组合，你怎么做？

稍微想想就会发现，大小为 2 的所有组合，不就是所有大小为 2 的子集嘛。

所以我说组合和子集是一样的：大小为 k 的组合就是大小为 k 的子集。

 

77. 组合 - 力扣（LeetCode）

class Solution {
 
  /**
     * 3.组合问题，找出给定数组中指定个数的组合
     *
     * @param n：指定范围1-n
     * @param k：指定个数k个
     * @return
     */
  List> res = new LinkedList<>();
// 记录回溯算法的递归路径
LinkedList track = new LinkedList<>();
 
// 主函数
public List> combine(int n, int k) {
    backtrack(1, n, k);
    return res;
}
 
void backtrack(int start, int n, int k) {
    // base case
    if (k == track.size()) {
        // 遍历到了第 k 层，收集当前节点的值
        res.add(new LinkedList<>(track));
        return;
    }
    
    // 回溯算法标准框架
    for (int i = start; i <= n; i++) {
        // 选择
        track.addLast(i);
        // 通过 start 参数控制树枝的遍历，避免产生重复的子集
        backtrack(i + 1, n, k);
        // 撤销选择
        track.removeLast();
    }
}
 
 
 }