面试
算法思想

回溯算法

# 算法思想 - 回溯算法

# 1. 概念

回溯法（Backtracking）和分枝限界法都属于基于搜索的算法，是对最简单“枚举法”的改进，用来避免大量无效的搜索。回溯法是一个不断“试错”的搜索过程，它会一步步地尝试构造问题的解，如果在某一步发现当前路径不可能得到问题的解（或者不满足题目的约束条件），就会“回溯”到上一步甚至更早的步骤，放弃之前做出的选择，尝试其它可能的搜索路径。因此，回溯算法也有“通用解题法”之称，适合用来解决一些组合数可能非常大的最优化或搜索类问题。

在实现上，回溯法通常用递归来完成，通过函数自身调用自身，实现对所有可能选择的逐一尝试和排除。它的执行过程可能有以下两种结果：

找到一个或多个满足要求的可行解或最优解；
尝试了所有可能的分步方法，却找不到满足要求的解，那么宣告无解。

回溯算法 vs. 深度优先搜索（DFS）

深度优先搜索（Depth First Search, DFS）是一种图或树的遍历或搜索方法，强调“先往深处走，再往广处走”，直到无法继续才回退到上一步继续尝试。
回溯算法 也使用“深度优先”的思想，只是在寻找特定解的过程中，会把已经走不通的路径剪掉，然后回退（回溯）到之前的选择点，继续尝试别的可能路径。回溯算法比单纯的遍历更注重“搜索的用途”，需要在搜索过程中判断是否可以早些放弃无效路径。

回溯算法可以看作是一种“带有剪枝的深度优先搜索”，在一些条件不满足时就立刻回退，从而大大减少不必要的搜索分支。

# 2. 搜索与遍历

我们日常使用的搜索引擎可以理解为：在庞大的信息库中找到我们想要的结果，本质上也是在大规模数据中进行搜索。回溯算法中的“搜索”与搜索引擎的“搜索”在概念上是一致的，都是 “在所有可能解中找到目标解”。

在算法领域，如果要搜集 “所有可能的解”，往往需要对 搜索空间 做一次全面的“遍历”，只不过不同的遍历方法会带来不同的搜索效率。因为回溯是利用 DFS（深度优先搜索）遍历整颗“搜索树”（或“状态树”），在中途会动态判断是否需要继续深入探索，或者提前剪枝。

有些人会称回溯算法为 “爆搜” 或者“暴力解法”，因为它本质上还是要考虑所有可能的路径，只不过利用了剪枝（见下节）来减少了很多不必要的计算。随着输入规模增大，如果没有充分的剪枝，暴力枚举很可能会超出时间限制；若通过精巧的剪枝策略，就能在实际运行中大幅减少搜索量。

# 3. 剪枝

“剪枝”是指在搜索过程中，遇到已经确定无法得到满足要求的解或者没有必要继续往下搜索的路径时，就直接 “剪掉” 不再继续搜索，从而减少不必要的搜索步骤。剪枝的好处在于能显著降低时间复杂度和空间复杂度的消耗，使得原本可能无法在时限内完成的搜索变得可行。

对于深度优先搜索（DFS）或广度优先搜索（BFS），如果不加任何判断直接遍历整棵搜索树，一旦搜索树的分支非常多，就会导致性能灾难。剪枝恰恰可以帮助我们在还没遍历到搜索树最深层时，就提前停止对某些无意义的分支的探索。

在回溯算法的实现中，我们往往是在 递归调用前 或 递归过程中 进行剪枝判断，如果发现当前路径不符合要求，就直接 return，避免做多余的递归和回退操作。

# 4. 回溯算法的基本“模板”

在实现回溯算法的时候，一般会保持下面几个要素：

解的存储结构：用来记录当前已经搜索到的结果（通常使用列表或数组等）。
搜索过程：使用递归的形式，每一层做出一项新的选择，并判断是否符合约束。
回退（回溯）：如果当前选择导致后续不可能得到可行解，就撤销当前选择，回到上一步，继续尝试下一种可能。

下面分别演示“元素允许重复”与“元素不允许重复”这两种常见场景下的回溯模板。请注意，以下代码仍然要根据具体问题进行改写，比如常见的全排列、组合、子集等问题，都可以在这个模板的基础上进行不同的扩展和剪枝策略。

# 4.1 元素允许重复

在这个例子里，我们假设数组 nums 中的元素可以被反复使用（或使用多次）。如果没有特殊的约束限制，那么我们可以在每一层（depth）选择任意一个元素。下面的例子中，我们演示一个最基本的思路：每深入一层，就把 nums[i] 放入 list 中，直到达到一定深度后，就把当前构造的序列加入结果集 ans 里。

class Solution {
    /**
     * 回溯算法示例：元素允许重复使用
     *
     * @param nums 输入数组
     * @return 所有可能的结果集合
     */
    public List<List<Integer>> solution(int[] nums) {
        int n = nums.length;
        List<List<Integer>> ans = new ArrayList<>();
        // 边界情况：若nums为空，直接返回空的结果集
        if (n == 0) {
            return ans;
        }
        
        // 用于存放当前路径（部分解）
        List<Integer> list = new ArrayList<>();
        // 从深度 0 开始搜索
        dfs(nums, n, list, 0, ans);
        return ans;
    }

    /**
     * @param nums  输入数组
     * @param n     数组长度
     * @param list  当前构造的路径（部分解）
     * @param depth 当前递归深度
     * @param ans   存放所有结果的集合
     */
    public void dfs(int[] nums, int n, List<Integer> list, int depth, List<List<Integer>> ans) {
        // 终止条件：当depth == n时，说明已经构造出长度为n的序列
        if (depth == n) {
            // 将当前构造的序列放入结果集中
            ans.add(new ArrayList<>(list));
            return;
        }
        
        // 这里以 "从i = depth到n" 为例，当然也有可能使用 "从0到n" 的循环方式
        for (int i = depth; i < n; i++) {
            // 1. 选择nums[i]
            list.add(nums[i]);
            
            // 2. 继续往下搜索（深度+1）
            dfs(nums, n, list, depth + 1, ans);
            
            // 3. 撤销当前选择（回溯）
            list.remove(list.size() - 1);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

代码说明

在 dfs 函数中，depth 用来表示已经选了多少个元素。当 depth == n 时，说明我们已经选满了 n 个元素，可以将当前路径 list 放入 ans。
回溯的关键点在于第三步“撤销当前选择（回溯）”，也就是 list.remove(list.size() - 1)。如果没有这一步，list 会一直累加，无法恢复到之前的状态。
这段示例仅用于演示回溯算法的结构，并没有实现剪枝。实际应用时，可结合题意进行各种条件判断以提高效率。

# 4.2 元素不允许重复

当题目要求“元素只能被使用一次”时，我们通常会用一个 used 数组（或 boolean 数组）来标记某个元素是否已经被选过。一旦某个元素被选过，就不能再选择它。

下面的代码演示了如何使用 used 数组进行标记和回溯：

public class Solution {
    /**
     * 回溯算法示例：元素不允许重复使用
     *
     * @param nums 输入数组
     * @return 所有可能的结果集合
     */
    public List<List<Integer>> solution(int[] nums) {
        int n = nums.length;
        List<List<Integer>> ans = new ArrayList<>();
        // 若nums为空，直接返回空集合
        if (n == 0) {
            return ans;
        }

        // 用来标记数组中的某个元素是否已经被使用
        boolean[] used = new boolean[n];
        // 当前路径（部分解）
        List<Integer> list = new ArrayList<>();

        // 从深度0开始
        dfs(nums, n, 0, list, used, ans);
        return ans;
    }

    /**
     * @param nums  输入数组
     * @param n     数组长度
     * @param depth 当前深度
     * @param list  当前路径
     * @param used  标记数组，对应nums中每个元素是否被使用过
     * @param ans   存放所有结果的集合
     */
    private void dfs(int[] nums, int n, int depth, List<Integer> list,
                     boolean[] used, List<List<Integer>> ans) {
        // 终止条件：如果当前路径长度 == n，说明已经选满了
        if (depth == n) {
            ans.add(new ArrayList<>(list));
            return;
        }

        // 在每一层，我们都尝试把nums[i]加进来
        for (int i = 0; i < n; i++) {
            // 如果nums[i]还没有被使用，则尝试使用它
            if (!used[i]) {
                // 1. 做出选择
                list.add(nums[i]);
                used[i] = true;

                // 2. 继续往下递归
                dfs(nums, n, depth + 1, list, used, ans);

                // 3. 撤销选择，回溯
                used[i] = false;
                list.remove(list.size() - 1);
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

代码说明

used[i] 表示下标为 i 的元素是否已经被选过。一旦被选过，就不会再在本层或者子层使用。
当 depth == n 时，说明已经选满了 n 个互不相同的元素，就可以将 list 拷贝加入结果集 ans。
回溯的关键在于“选择—递归—回退”的三个过程。每一层只要将 used[i] 更新为 true 后，深度搜索结束再把它还原回 false，就能保证所有可能的组合都被遍历到。
同样，这里也可以根据具体题目添加更多的剪枝逻辑，例如在某些场景下，如果我们当前选择不可能得到比已有答案更好的解，就可以提前剪掉该分支。

# 5. 回溯算法总结

回溯算法核心：深度优先 + 回退 + 剪枝
- 先往深处探寻可能的解；
- 发现走不通时立即回退；
- 通过剪枝降低搜索空间。
实现方式：基于递归来实现。因为递归天然具有“入栈出栈”的行为，正好对应回溯算法中的“选择”和“撤销选择”这两个动作。
应用场景：全排列、组合、子集、棋盘问题（如 N 皇后）、数独求解、路径搜索、背包问题等等，只要题目本质上是“在某棵搜索树中找解”，基本都能用回溯思想来解决。
性能优化：
- 剪枝是回溯中极其重要的思想；
- 另外还可以结合 记忆化搜索、动态规划 等其他思想，进一步减少重复搜索。
注意事项：
- 回溯算法容易在细节上出错，比如“回退”步骤少写或写错，就会导致错误的结果或重复的解；
- 在大规模数据时，如果剪枝不充分，依然可能超时；
- 要根据具体问题设置剪枝条件，才能大大提升效率。

回溯算法的学习更多是要多写、多调试。在实际项目中，回溯也常常与其他算法思路（如贪心、DP、搜索框架）结合使用，从而最大程度地提升效率。

# 6. 小试牛刀

# 6.1 组合总和

LeetCode 39. 组合总和 (opens new window)

# 1. 题目描述

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取。
如果至少一个数字的被选数量不同，则两种组合视为不同。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例：

输入：candidates = [2,3,6,7], target = 7 输出：[[2,2,3],[7]]
输入：candidates = [2,3,5], target = 8 输出：[[2,2,2,2],[2,3,3],[3,5]]
输入：candidates = [2], target = 1 输出：[]

# 2. 思路分析

由于题目允许 同一个数字可以无限制地被选取，我们常用 DFS（深度优先搜索）+ 回溯的方式来搜索所有可能的组合。每走到一条“路径”时，通过将当前数字减去目标值 target，如果 target 变为 0，说明当前路径恰好满足条件；如果 target 小于 0，说明已经超出，直接返回（回溯）。这样就能收集到所有符合条件的组合。

需要注意的地方：

为了避免出现重复组合，我们在递归时常会记录一个 begin 参数，控制本层递归只能从 begin 开始向后搜索，不再回头。这能防止像 [2,3] 和 [3,2] 这样排列顺序不同、但组合结果相同的重复结果。
如果加上排序，就可以轻松进行“剪枝”：当 candidates[i] > target 时，后面的数也没必要再尝试。

下面给出三段代码：

最基础版本（无剪枝）
带剪枝版本（排好序后剪枝）
另一种 DFS 顺序（从后往前遍历）

# 2.1 基础版本（无剪枝）

public class Solution {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int len = candidates.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }

        // 使用双端队列可以在两端进行高效的插入、删除操作
        Deque<Integer> path = new ArrayDeque<>();
        
        // 从数组下标0开始搜索
        dfs(candidates, 0, len, target, path, res);
        return res;
    }

    /**
     * @param candidates  候选数组
     * @param begin       本层递归的搜索起点（控制不重复）
     * @param len         数组长度
     * @param target      剩余要凑成的目标值
     * @param path        当前路径，存放已经选过的数字
     * @param res         结果集，用于收集所有满足要求的组合
     */
    private void dfs(int[] candidates, int begin, int len, int target,
                     Deque<Integer> path, List<List<Integer>> res) {
        // 若 target < 0，说明当前路径和超过了目标值，直接返回
        if (target < 0) {
            return;
        }
        // 若 target == 0，说明已经凑出了一组和为 target 的组合
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        // 从 begin 开始，尝试所有可能的候选数字
        for (int i = begin; i < len; i++) {
            // 1. 选择 candidates[i]
            path.addLast(candidates[i]);
            // 2. DFS：因为数字可以无限制重复使用，因此下一层递归仍然是 i 而非 i+1
            dfs(candidates, i, len, target - candidates[i], path, res);
            // 3. 回溯：撤销选择
            path.removeLast();
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

代码要点：

begin 参数确保了组合不会因为元素顺序不同而重复。
当 target - candidates[i] < 0 时，没有必要继续往下走（无剪枝版本里虽然没有 break，但是也会自然返回）。

# 2.2 带剪枝版本（需先排序）

public class Solution {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int len = candidates.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }

        // 为了实现剪枝，先对候选数组进行排序
        Arrays.sort(candidates);

        Deque<Integer> path = new ArrayDeque<>();
        dfs(candidates, 0, len, target, path, res);
        return res;
    }

    private void dfs(int[] candidates, int begin, int len, int target,
                     Deque<Integer> path, List<List<Integer>> res) {
        // 当 target == 0 时，找到一组可行解
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        // 从 begin 开始，向后搜索
        for (int i = begin; i < len; i++) {
            // 剪枝：若 candidates[i] > target，则后面更大的 candidates[i+1], candidates[i+2]... 更不可能满足
            if (candidates[i] > target) {
                break;  // 直接跳出循环
            }

            // 1. 选择 candidates[i]
            path.addLast(candidates[i]);
            // 2. DFS，这里依然传 i 而不是 i+1
            dfs(candidates, i, len, target - candidates[i], path, res);
            // 3. 撤销选择
            path.removeLast();
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

代码要点：

在数组已经有序的情况下，如果 candidates[i] > target，可以直接 break，大大减少搜索范围。
其他逻辑与无剪枝版本类似。

# 2.3 另一种 DFS 顺序（从后往前遍历）

有时，为了实现不同的搜索顺序（或者出于题目特殊需求），我们可以先往深处走到末尾，再从后向前回溯。思路一致，只是参数设置略有不同。

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        // 从深度为0开始，构造一个当前路径list
        dfs(candidates, ans, target, 0, new ArrayList<>());
        return ans;
    }

    /**
     * @param candidates  候选数组
     * @param ans         存放结果的List
     * @param target      当前剩余的目标值
     * @param deep        当前递归深度，用于控制数组下标
     * @param list        当前路径
     */
    public void dfs(int[] candidates, List<List<Integer>> ans, int target,
                    int deep, List<Integer> list) {
        // 如果越界，直接返回
        if (deep == candidates.length) {
            return;
        }
        // 如果恰好凑成 target = 0，收集当前路径
        if (target == 0) {
            ans.add(new ArrayList<>(list));
            return;
        }
        
        // 1. 不选当前 candidates[deep]，向下搜索
        dfs(candidates, ans, target, deep + 1, list);

        // 2. 若还能选当前数字（target - candidates[deep] >= 0）
        if (target - candidates[deep] >= 0) {
            list.add(candidates[deep]);
            // 这里仍然是 deep 而不是 deep+1，因为可以无限制选用同一个数字
            dfs(candidates, ans, target - candidates[deep], deep, list);
            // 回溯
            list.remove(list.size() - 1);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

# 6.2 全排列

LeetCode 46. 全排列 (opens new window)

# 1. 题目描述

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

示例：

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

# 2. 思路分析

全排列要求的是将数组 nums 中的所有元素按照各种顺序排列起来。

可以理解为搜索一棵 “状态树”，每个节点做出“选择某个数字加入当前排列”的决定。
因为 元素不可重复，可以使用一个 used[] 数组来标记当前元素是否被选用；或者通过“交换”来动态维护未确定的部分。
当已经选满（选了 n 个数字）时，将当前结果存入答案集。

下面依次展示三种典型写法：

# 2.1 使用 `used[]` 数组+回溯

public class Solution {

    public List<List<Integer>> permute(int[] nums) {
        int len = nums.length;
        // 存放所有的结果
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }

        // 标记某个下标是否使用过
        boolean[] used = new boolean[len];
        // 用来记录当前路径
        Deque<Integer> path = new ArrayDeque<>(len);

        dfs(nums, len, 0, path, used, res);
        return res;
    }

    /**
     * @param nums  原数组
     * @param len   数组长度
     * @param depth 当前已经选了多少个元素
     * @param path  当前路径，存放已经选择的数字
     * @param used  标记数组，used[i] 表示 nums[i] 是否已经被选过
     * @param res   结果集，收集所有的排列
     */
    private void dfs(int[] nums, int len, int depth,
                     Deque<Integer> path, boolean[] used,
                     List<List<Integer>> res) {
        // 当 depth == len，说明已经选满了
        if (depth == len) {
            // 把当前构造的排列放入结果集
            res.add(new ArrayList<>(path));
            return;
        }

        // 尝试选用 nums[i]
        for (int i = 0; i < len; i++) {
            if (!used[i]) {
                // 1. 选择 nums[i]
                path.addLast(nums[i]);
                used[i] = true;

                // 2. 继续搜索下一个位置
                dfs(nums, len, depth + 1, path, used, res);

                // 3. 回溯（撤销选择）
                used[i] = false;
                path.removeLast();
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

代码要点：

depth 表示当前选了多少元素，若已经选了 len 个，就表示已经形成了一种排列。
通过 used[]，保证同一个数字不会在同一条搜索路径中被重复选到。

# 2.4 用新建变量替换回溯（空间换时间）

这一写法思路相同，只是 每一次递归都新建一个 path 和一个 used**，这样就不需要“回溯”操作，代码也更简洁，但会消耗更多的内存。

public class Solution {

    public List<List<Integer>> permute(int[] nums) {
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }

        boolean[] used = new boolean[len];
        List<Integer> path = new ArrayList<>();

        dfs(nums, len, 0, path, used, res);
        return res;
    }

    private void dfs(int[] nums, int len, int depth,
                     List<Integer> path, boolean[] used,
                     List<List<Integer>> res) {
        // 当已经选满
        if (depth == len) {
            // 这里可以直接把 path 加入 res，因为 path 在这里不会再被修改
            res.add(path);
            return;
        }

        // 逐个尝试
        for (int i = 0; i < len; i++) {
            if (!used[i]) {
                // 1. 新建当前层的 path 和 used，从而不需要回溯
                List<Integer> newPath = new ArrayList<>(path);
                newPath.add(nums[i]);
                boolean[] newUsed = new boolean[len];
                System.arraycopy(used, 0, newUsed, 0, len);
                newUsed[i] = true;

                // 2. DFS
                dfs(nums, len, depth + 1, newPath, newUsed, res);
                // 3. 无需回溯
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

代码要点：

每次递归都新开 ArrayList 和 boolean[]，避免“回溯”操作的同时，也导致额外的时间、空间开销。
在大型数据下，这样写可能会更慢，一般不推荐。

# 2.3 通过交换来生成全排列

在某些题解或算法书中，常见一种“就地操作”的思路：将数组的第 start 个元素与第 i 个元素交换，递归处理 start+1，再交换回来。这样就不需要 used[] 数组。

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        
        // 先把 nums 的所有元素放到一个 List 中，方便后续 swap
        List<Integer> list = new ArrayList<>();
        for (int num : nums) {
            list.add(num);
        }
        
        // 从下标 0 开始进行全排列
        dfs(nums.length, list, 0, ans);
        return ans;
    }

    /**
     * @param n      数组长度
     * @param list   将数组元素放入列表中，方便做 swap 操作
     * @param start  当前递归要确定的位置索引
     * @param ans    存放最终结果的列表
     */
    public void dfs(int n, List<Integer> list, int start, List<List<Integer>> ans) {
        // 当 start == n，说明前面所有位置都已经确定好
        if (start == n) {
            // 将当前 list 的一个拷贝作为一个全排列放入结果集
            ans.add(new ArrayList<>(list));
            return;
        }

        // 尝试让当前位置 start 和 i 的元素进行交换
        for (int i = start; i < n; i++) {
            // 1. 交换，使得 nums[start] 固定为下一个选择
            Collections.swap(list, start, i);
            // 2. 继续确定下一个位置
            dfs(n, list, start + 1, ans);
            // 3. 回溯：交换回来
            Collections.swap(list, start, i);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

代码要点：

start 代表下一步要确定哪个位置上的元素。
每一层都会将 list[start] 与 list[i] 交换，让 i 位置上的数固定到 start，然后再去确定下一个位置。
回溯时，用 Collections.swap(list, start, i) 交换回来，保证不会影响上一层的状态。

编辑此页

上次更新: 2025/01/05, 02:09:04

← 贪心算法分治算法→

回溯算法

# 算法思想 - 回溯算法

# 1. 概念

# 2. 搜索与遍历

# 3. 剪枝

# 4. 回溯算法的基本“模板”

# 4.1 元素允许重复

# 4.2 元素不允许重复

# 5. 回溯算法总结

# 6. 小试牛刀

# 6.1 组合总和

# 1. 题目描述

# 2. 思路分析

# 2.1 基础版本（无剪枝）

# 2.2 带剪枝版本（需先排序）

# 2.3 另一种 DFS 顺序（从后往前遍历）

# 6.2 全排列

# 1. 题目描述

# 2. 思路分析

# 2.1 使用 used[] 数组+回溯

# 2.4 用新建变量替换回溯（空间换时间）

# 2.3 通过交换来生成全排列

# 2.1 使用 `used[]` 数组+回溯