回溯模板

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

回溯算法核心就是遍历多叉树

排列组合

46. 全排列 - 力扣（LeetCode）

给定一个不含重复数字的数组 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]]

​ 排列回溯的时候每次都要从第一个开始遍历，遇到遍历过的需要用visited记录，避免重复使用元素

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] visited;
    public List<List<Integer>> permute(int[] nums) {
         visited = new boolean[nums.length];
        dfs(nums,0,visited);
        return res;
    }
    void dfs(int[] nums,int start,boolean[] visited){
        if(path.size() == nums.length){
            res.add(new ArrayList<>(path));
            return;
        }
        //回溯
        for(int i = 0;i < nums.length;i++){
            if(visited[i]){
                continue;
            }
            visited[i] = true;
            path.add(nums[i]);
            dfs(nums,i + 1,visited);
            path.remove(path.size() - 1);
            visited[i] = false;
        }
    }
}

77. 组合 - 力扣（LeetCode）

给定两个整数 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]]

​ 组合回溯不走回头路，从start开始

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    List<Integer> path = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        traceBack(n,k,1);
        return res;
    }
    void traceBack(int n, int k,int start){
        if(path.size() == k){
            res.add(new LinkedList<>(path));
            return;
        }
        for(int i = start; i <=n;i++){
            path.add(i);
            traceBack(n,k,i+1);
            path.remove(path.size() - 1);
        }
    }
}

组合可复选

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

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

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int sum = 0;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(candidates, 0, target);
        return res;
    }

    void dfs(int[] candidates, int start, int target) {
        if (sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }
        if (sum > target) {
            return;
        }
        //可以复选，但是不能走回头路，所以i还是要从start开始
        for (int i = start; i < candidates.length; i++) {
            path.add(candidates[i]);
            sum += candidates[i];
            //如果还是dfs(candidates, i + 1, target)，就没有复选当前元素，i+1是递归之前就移动到下一个元素了，i是等递归结束返回的时候再+1
            dfs(candidates, i , target);
            sum -= candidates[i];
            path.remove(path.size() - 1);
        }
    }
}

candidates = [2,3,6,7], target = 7的递归图

dfs([], sum=0, start=0)
│
├── 选择 2 → dfs([2], sum=2, start=0)
│   │
│   ├── 选择 2 → dfs([2, 2], sum=4, start=0)
│   │   │
│   │   ├── 选择 2 → dfs([2, 2, 2], sum=6, start=0)
│   │   │   │
│   │   │   ├── 选择 2 → dfs([2, 2, 2, 2], sum=8) ✘ sum > target 回溯
│   │   │   └── 选择 3 → dfs([2, 2, 2, 3], sum=9) ✘ 回溯
│   │   │       选择 6 → sum=12 ✘
│   │   │       选择 7 → sum=13 ✘
│   │   │
│   │   ├── 选择 3 → dfs([2, 2, 3], sum=7) ✔ 找到解
│   │   ├── 选择 6 → sum=10 ✘
│   │   └── 选择 7 → sum=11 ✘
│   │
│   ├── 选择 3 → dfs([2, 3], sum=5, start=1)
│   │   ├── 选择 3 → dfs([2, 3, 3], sum=8) ✘
│   │   ├── 选择 6 → sum=11 ✘
│   │   └── 选择 7 → sum=12 ✘
│   │
│   ├── 选择 6 → dfs([2, 6], sum=8) ✘
│   └── 选择 7 → dfs([2, 7], sum=9) ✘
│
├── 选择 3 → dfs([3], sum=3, start=1)
│   ├── 选择 3 → dfs([3, 3], sum=6, start=1)
│   │   ├── 选择 3 → dfs([3, 3, 3], sum=9) ✘
│   │   ├── 选择 6 → sum=12 ✘
│   │   └── 选择 7 → sum=13 ✘
│   ├── 选择 6 → sum=9 ✘
│   └── 选择 7 → sum=10 ✘
│
├── 选择 6 → dfs([6], sum=6, start=2)
│   ├── 选择 6 → sum=12 ✘
│   └── 选择 7 → sum=13 ✘
│
└── 选择 7 → dfs([7], sum=7, start=3) ✔ 找到解

N皇后问题

52. N 皇后 II - 力扣（LeetCode）

n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。

示例 1：

输入：n = 4
输出：2
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：1

提示：

• `1 <= n <= 9

class Solution {
    int res = 0;
    boolean[] col;
    boolean[] diag1, diag2;

    public int totalNQueens(int n) {
        col = new boolean[n];
        diag1 = new boolean[2 * n - 1];
        diag2 = new boolean[2 * n - 1];
        dfs(0, n);
        return res;
    }

    void dfs(int row, int n) {
        if(row == n){
            res++;
            return;
        }
        for (int c = 0; c < n; c++) {
            //可能会有row - c < 0，所以在此基础上加一个偏移量(n - 1)
            if(col[c] || diag1[row - c + n - 1] || diag2[row + c]) continue;
            col[c] = true; diag1[row - c + n - 1] = true; diag2[row + c]=true;
            dfs(row + 1,n);
            col[c] = false; diag1[row - c + n - 1] = false; diag2[row + c]=false;
        }
    }
}

主对角线x-y是一个常量，副对角线x+y是一个常量

证明：为什么主对角线x-y是一个常量

令一个格子坐标为 (r, c)（0 ≤ r, c < n）。主对角线是从左上到右下的方向（↘）。 如果两个格子 (r1, c1) 和 (r2, c2) 在同一条主对角线上，那么它们在行方向和列方向的增量相等：

$$r2−r1=c2−c1$$

两边同时移项得

$$r2−c2=r1−c1$$

同理：副对角线是从右上到左下的方向（↙）。若 (r1,c1) 和 (r2,c2) 在同一条副对角线，则行增量和列增量方向相反：

$$r2−r1=−(c2−c1)$$

整理得

$$r2+c2=r1+c1$$

因此副对角线上 r + c 恒定 —— 用 row + col 来标识副对角线也是正确且充分的。

两个不同元素选择要或者不要

22. 括号生成 - 力扣（LeetCode）

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

提示：

• 1 <= n <= 8

class Solution {
    List<String> res = new ArrayList<>();
    StringBuilder path = new StringBuilder();

    public List<String> generateParenthesis(int n) {
        dfs(n,n);
        return res;
    }

    void dfs(int left, int right) {
        if(right < left) return;
        if(left < 0 || right < 0) return;
        if (left ==  0 && right == 0) {
            res.add(path.toString());
            return;
        }
        //回溯左括号要不要
        path.append('(');
        dfs(left - 1,right);
        path.deleteCharAt(path.length() - 1);
        //回溯右括号要不要
        path.append(')');
        dfs(left,right - 1);
        path.deleteCharAt(path.length() - 1);
    }
}

编辑此页

贡献者: scrazyakai

上一页字典树

下一页JDK8项目中引入千问AI