算法训练营（day24）

回溯理论基础

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

回溯算法理论基础

回溯算法的理解

回溯法解决的问题都可以抽象为树形结构：回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。

因此回溯法可以理解为：

  1. 首先沿着一条子树走到末尾
  2. 记录这一条路径，再返回这条子树 叶子节点 的父节点
  3. 如果 父节点 还有别的 叶子节点，则记录为 另外一条路径
  4. 如果 父节点 的叶子节点都记录完毕，则继续 向上 找 父节点，循环这个过程
  5. 直到整棵树都被遍历，返回 满足要求的路径及结果

排列&组合

排列有序，组合无序

回溯算法模板

1
2
3
4
5
6
7
8
9
10
11
12
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

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

77. 组合

题目链接：https://leetcode.cn/problems/combinations/description/

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

解题思路

解题过程：回溯

  1. 定义终止条件
  2. 定义递归方法
  3. 对叶子节点进行 回溯

详细代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> combine(int n, int k) {
        backTrack(n, k, 1);
        return result;
    }

    public void backTrack(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);
            backTrack(n, k, i + 1);
            path.removeLast();	//回溯
        }
    }
}