2025/10/2大约 6 分钟
回溯
回溯模板
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择回溯算法核心就是遍历多叉树
排列组合
给定一个不含重复数字的数组 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;
}
}
}给定两个整数 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);
}
}
}组合可复选
给你一个 无重复元素 的整数数组
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皇后问题
n 皇后问题 研究的是如何将
n个皇后放置在n × n的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数
n，返回 n 皇后问题 不同的解决方案的数量。示例 1：
img 输入：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 来标识副对角线也是正确且充分的。
两个不同元素选择要或者不要
数字
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);
}
}