回溯算法之组合和排列问题

文章目录

1.什么是回溯算法
2.回溯算法解题步骤
3.回溯算法解决组合问题
4.回溯算法解决排列问题

1.什么是回溯算法

回溯算法是一种通过尝试所有可能的解决方案来解决问题的算法策略，它通常用于求解组合优化、排列组合、路径搜索等类型的问题,是一种暴力求解的算法。

2.回溯算法解题步骤

回溯算法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为 “回溯点”。

回溯算法的解题步骤如下：

路径：记录已经做过的选择。
选择列表：当前可以做出的选择。
结束条件：到达决策树的底层，无法再做选择的条件。

回溯算法中最经典的就是组合和排列问题。

3.回溯算法解决组合问题

组合的定义

从 n 个不同元素中取出 m个元素组成一组，不考虑元素的顺序，这样的一组元素就叫做从 n 个不同元素中取出 m 个元素的一个组合。

题目来自于https://leetcode.cn/problems/combinations/description/

题目描述：

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按任何顺序返回答案。

示例1：

输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

画图分析：
图为示例 1的情况下，当n = 4,k=2时，我们需要在[1,4]之间取出两个数组合：
在这里插入图片描述
用暴力求解的思想，我们很容易想到可以用两成for循环去做，但这题的n和k是动态的，想要控制好循环的层数，还是挺难的。
这个时候就需要使用到回溯算法了，先来看以下代码：

class Solution {
    public List<List<Integer>> result = new ArrayList<>();
    public List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        backTracking(n,k,1);
        return result;
    }
    public void backTracking(int n,int k,int startIndex){
        if(path.size() == k){
            result.add(new ArrayList<>(path));
            return;
        }
        for(int i = startIndex;i <= n-(k-path.size())+1;i++){
            path.add(i);
            backTracking(n,k,i+1);
            path.removeLast();
        }
    }
}

图解上述代码流程：
在这里插入图片描述

result：用于存储最终的所有组合结果，是一个二维列表，每个子列表代表一个组合。
path：用于存储路径上的值。

在循环过程中

首先将当前数字 i 添加到 path 中。
递归调用 backTracking 方法，继续生成下一个数字的组合，起始索引更新为 i + 1。
满足终止条件就收集数据，返回到上一次递归中进行回溯。
回溯操作，将最后添加的数字从 path 中移除，以便尝试其他可能的组合。

循环条件中的i <= n-(k-path.size())+1是为了剪枝。
来看一种极端情况，假设n = 4,k =4.
在这里插入图片描述
那么除了一开始的[1,2,3,4]其它情况都没必要遍历。在添加i <= n-(k-path.size())+1这个条件后，刚开始执行backTracking，我们就保证了i是小于等于1的，比1大的情况，组合的结果个数都小于4。

4.回溯算法解决排列问题

排列定义：

从 n 个不同元素中取出 m 个元素，按照一定的顺序排成一列，叫做从 n 个不同元素中取出 m 个元素的一个排列。当 n =m 时，称为全排列。

题目来自：https://leetcode.cn/problems/permutations/description/

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。你可以按任意顺序返回答案。

示例1:

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例2:

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例3:

输入：nums = [1]
输出：[[1]]

以示例1来分析：
在这里插入图片描述
这一题其实和第一题类似，上一题的for循环要从当前位置的下一个位置开始，而这一题需要从头开始遍历，并且不能等于当前的值。
代码如下所示：

class Solution {
    public List<List<Integer>> result = new ArrayList<>();
    public ArrayList<Integer> path = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        backTracking(nums);
        return result;
    }

    public void backTracking(int[] num){
        if(path.size() == num.length){
            result.add(new ArrayList<>(path));
            return;
        }
        for(int i = 0;i < num.length;i++){
            if(path.contains(num[i])){
                continue;
            }
            path.add(num[i]);
            backTracking(num);
            path.remove(path.size()-1);
        }
    }
}