随想录日记part20

$time：$ 2024.03.15

---

---

主要内容：今天开始就要开始学习回溯算法了，今天主要学习其基本理论以及在组合问题中的应用。

• 理论基础
• 第77题. 组合

---

---

Topic1理论基础

1.回溯算法的题目分类：

2.回溯的定义：

回溯法也可以叫做回溯搜索法，它是一种搜索的方式。回溯是递归的副产品，只要有递归就会有回溯。

3.回溯的效率：

回溯法并不是什么高效的算法。因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。

4.回溯法解决的问题:

• 组合问题：N个数里面按一定规则找出k个数的集合
• 切割问题：一个字符串按一定规则有几种切割方式
• 子集问题：一个N个数的集合里有多少符合条件的子集
• 排列问题：N个数按一定规则全排列，有几种排列方式
• 棋盘问题：N皇后，解数独等等

5.回溯法模板:

1.回溯函数模板返回值以及参数
回溯函数伪代码如下：

void backtracking(参数)

2.回溯函数终止条件
回溯函数终止条件伪代码如下：

if (终止条件) {
    存放结果;
    return;
}

3.回溯搜索的遍历过程
回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。如图：

回溯函数遍历过程伪代码如下：

for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
    处理节点;
    backtracking(路径，选择列表); // 递归
    回溯，撤销处理结果
}

整个模板流程如下：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

---

---

Topic2组合

题目：

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

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

思路： 按照回溯模板我们进行回溯三部曲：
递归三部曲：

1.回溯函数模板返回值以及参数
在这里要定义两个全局变量，$path$用来存放符合条件单一结果，$result$用来存放符合条件结果的集合。回溯函数里一定有两个参数，既然是集合 $n$ 里面取 $k$ 个数，那么 $n$ 和$k$ 是两个 $int$ 的参数。还需要一个参数为 $int$ 型变量 $startIndex$，这个参数用来记录本层递归的中，集合从哪里开始遍历（集合就是 $[1,...,n]$ ）。
所以整体代码如下：

List<List<Integer>> result=new ArrayList<>();
LinkedList<Integer> path=new LinkedList<>();
private void backtracking(int n,int k, int statindex){}

2.回溯函数终止条件
回溯出口，如果 $Path$ 里面的数量等于 $K$，说明其到达叶子节点
代码如下：

if(k==path.size()){//回溯出口，如果Path里面的数量等于K，说明其到达叶子节点
	result.add(new ArrayList<>(path));
    return;
}

3.回溯搜索的遍历过程
$for$ 循环每次从 $startIndex$ 开始遍历，然后用 $path$ 保存取到的节点i搜索的过程如下图：

实现代码如下：

for(int i=startindex;i<=n;i++){
            path.add(i);
            backtracking(n,k,i+1);
            path.removeLast();
        }

完整的代码如下：

class Solution {
    List<List<Integer>> result=new ArrayList<>();
    LinkedList<Integer> path=new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        result.clear();
        path.clear();
        backtracking(n,k,1);
        return result;
    }
    private void backtracking(int n,int k, int startindex){
        if(k==path.size()){//回溯出口，如果Path里面的数量等于K，说明其到达叶子节点
            result.add(new ArrayList<>(path));
            return;
        }
        for(int i=startindex;i<=n;i++){
            path.add(i);
            backtracking(n,k,i+1);
            path.removeLast();
        }
    }
}

时间复杂度: $O(n\ast 2^n)$
空间复杂度: $O(n)$

上述代码还能进行进一步的剪枝：
如果 $for$ 循环选择的起始位置之后的元素个数已经不足我们需要的元素个数了，那么就没有必要搜索了，举个例子：

• 已经选择的元素个数：$path.size()$;
• 还需要的元素个数为: $k-path.size()$;
• 在集合$n$中至多要从该起始位置 : $n-(k-path.size())+1$，开始遍历 (至于为什么写$n-(k-path.size())+1$，可以简单例子带入就能检测，这样可以使得我们精准的写好代码)
  完整剪枝后的代码:

class Solution {
    List<List<Integer>> result=new ArrayList<>();
    LinkedList<Integer> path=new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        result.clear();
        path.clear();
        backtracking(n,k,1);
        return result;
    }
    private void backtracking(int n,int k, int startindex){
        if(k==path.size()){//回溯出口，如果Path里面的数量等于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();
        }
    }
}