回溯算法 | wittleLuna

2025-06-11

回溯和递归相辅相成，本质上是暴力查找算法(穷举)，所有的回溯法都可以抽象为树形结构

回溯法，一般可以解决如下几种问题：

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

模板框架:

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

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

回溯三部曲: 1.确定递归函数的参数和返回值 2.确定递归的终止条件 3.确定单层搜索的逻辑

一般返回值都为void

组合问题

==需要startIndex来保证元素不被重复选取==

组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按任何顺序返回答案。
示例 1：
输入：n = 4, k = 2 输出： [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

确定参数和返回值：

参数：n:代表遍历的次数 k:代表需要走到的深度 startIndex: 代表当前层的遍历位置(因为是组合问题，每个节点只能从其之后的位置开始遍历)
返回值：none, 使用全局遍历存储结果和当前路径的元素

确定递归终止条件：

如果当前路径的元素=当前的深度：说明找到的元素个数符合要求，那么把当前路径作为一种结果加入结果变量，之后返回

确定单层的递归逻辑：

for循环，加入当前的元素，之后递归进行下一层循环，注意循环开始的位置，之后回溯去掉当前加入的元素（删除当前元素，之后回溯加入其他元素）

剪枝优化:

如果k 和 n 相等，如4,4 那么整个递归只有一种可能。但是当前的程序仍然会尝试每个分支，返回符合结果要求的路径。所以可以考虑进行剪枝优化
如何剪枝：如果循环位置开始时的剩余元素不满足题目里，减去当前元素，k的个数，for循环就不进行
- 具体for循环条件上实现:
  1.起始位置: i = startIndex 2.终止条件: i <= n- (k - path.size()) + 1

n- (k - path.size()) + 1 理解 : 限制能继续循环的次数

path.size() : 当前节点已经有的元素数量
k - path.size(): 满足条件剩余需要的元素数量
n - (k - path.size()): [1-n]全部元素里，剩余可选元素的数量
n - (k - path.size()) + 1: [1-n]全部元素里，除去当前节点需要选择的元素，剩余可选元素的数量
本题递归每层for循环的个数是不固定的

代码实现

List<List<Integer>> result= new ArrayList<>();
	LinkedList<Integer> path = new LinkedList<>();
	
	public List<List<Integer>> combine(int n, int k)  {
		
		backtracking(1, n, k);
		
		return result;
		
	}
	
	
	public void backtracking(int startIndex, int n,int k) {
		
		if(path.size() == k) {
			result.add(new ArrayList<>(path));
			return;
		}
		// 优化，如果剩余的元素数量不满足要求，不进行之后的遍历
        // +1 ： 当前的元素需要遍历
		for(int i = startIndex; i <= n - (k - path.size()) + 1 ; i++) {
			path.add(i);
			backtracking(i + 1, n, k);
			path.removeLast();
		}
		
		
	}

组合总和 III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9 每个数字最多使用一次返回所有可能的有效组合的列表。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
示例 1:
输入: k = 3, n = 7 输出: [[1,2,4]] 解释: 1 + 2 + 4 = 7 没有其他符合的组合了。

确定参数和返回值：

n, 用于判断此时是否得到合适的和
k,用于判断当前元素数量（或路径深度）是否满足要求
startIndex,确定每次for循环的起始位置
sum,得到每个节点计算的和

终止条件:

如果当前元素数量满足要求，并且sum == n, 就把当前路径作为答案之一加入答案数组

//朴素想法
if(path.size() == k && sum == n) {
			result.add(new ArrayList<>(path));
			return;
		}

//更优写法，直接返回，避免了不必要回溯的过程
if (path.size() == k) {
    if (sum == targetSum) result.push_back(path);
    return; // 如果path.size() == k 但sum != targetSum 直接返回
}

单层递归逻辑:

1.把当前元素加入path 2.sum += 当前元素 3.递归 4.回溯，sum -= 当前元素， path.removeLast()移除当前元素

剪枝优化

1.节点剪枝

如果此时的sum已经大于n,继续递归没有意义

if(sum > n) { // 剪枝操作，如果此时的和大于n， 就没必要继续递归
				sum -= i;
				path.removeLast();
				return;
			}

2.for循环范围剪枝

和上一题类似，可写为 i <= 9 -( k - path.size()) + 1

代码实现

List<List<Integer>> result= new ArrayList<>();
	LinkedList<Integer> path = new LinkedList<>();
	
	public List<List<Integer>> combinationSum3(int k, int n) {
		
		backtracking(1, n, k, 0);
		
		return result;
		
	}
	
	public void backtracking(int startIndex, int n, int k, int sum) {
		
		if(path.size() == k && sum == n) {
			result.add(new ArrayList<>(path));
			return;
		}
		//for循环的范围剪枝
		for(int i = startIndex;  i <= 9 - (k - path.size()) + 1  ; i++) {
			path.add(i);
			sum += i;
            if(sum > n) { // 剪枝操作，如果此时的和大于n， 就没必要继续递归
				sum -= i;
				path.removeLast();
				return;
			}
			backtracking(i + 1, n, k, sum);
			sum -= i;
			path.removeLast();
		}
		
		
	}

电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = “23” 输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

参数和返回值

假设使用for循环解决这道问题:当digits=“23”,那么需要使用双层for循环，外层for遍历2对应字符，内层对应3对应字符，得到每两个的字符组合，最终得到答案。

使用回溯的思路，可以想到，每层for循环就是一层递归，当前选取的元素就是对应当前digits数字对应字符中的所有字符。参数:需要的总深度n(也就是字符串长度), 数字对应字符串的数组digits[]，用于确定当前层使用的for循环数组，当前所在的深度length(用于确定是否达到终止条件)，当前digits数字d,用于确定遍历哪个数组。

返回值:void

递归终止条件

如果此时length == n,说明达到需要深度，把结果加入result中，返回

单层递归逻辑

每次for循环的循环次数为对应d数组中的每个元素(和上两题不同，不需要startindex来确定启始位置，因为每次都需要遍历数组中所有的元素，从0开始)。

1.在path(可用一个stringbuilder 来作为path)里加入当前字符

2.递归，进入下一层，length+1,对应digits进入下一位

3.回溯，从path中删去当前字符

最好这样先加入，递归，回溯这样写。而不是for循环中，直接在递归里写进入下一层加入，做到回溯效果，这样比较明显，且好理解

代码实现

 List<String> result= new ArrayList<>();
	StringBuilder path = new StringBuilder();
	
	public List<String> letterCombinations(String digits)  {
		
		String[] keyboard = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
		
		int length = digits.length();
		
		char[] num = digits.toCharArray();
		
		backtracking(length, num, keyboard , 0);
		
		return result;
	}
	
	
	public void backtracking(int length, char[] num, String[] keyboard , int n) {
		
		if(length == 0) {
			return;
		}
		
		if(n == length) {
			result.add(path.toString());
			return;
		}
		
		for(int i = 0; i < keyboard[num[n] - '0' - 2].length(); i++) {
			path.append(keyboard[num[n] - '0' - 2].charAt(i));
			
			backtracking(length, num, keyboard , n + 1);
			
			path.deleteCharAt(path.length() - 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 。仅有这两种组合。

参数和返回值

参数：

sum: 要求和为target，所以自然参数中需要传递每层的sum的值
startIndex: 需要控制for循环的起始位置。同一个数字可以重复使用，组合问题，所以每层for循环的起点应该从自己开始
candidates[]: 用于获取数据，也可以作为全局变量，不作为参数

终止条件

sum == target时，把当前节点结果加入结果数组中，返回

单层递归逻辑

1.在path中加入当前candidates中对应的元素

2.sum += candidates[i]

3.递归，注意此时startIndex应该为i

4.回溯，path路径中删去当前candidates中对应的元素

5.sum -= candidates[i]

剪枝优化

从图中可以看出，如果sum>target时，此时for循环无需继续进行

for循环范围剪枝思路：

先对数组进行排序，在回溯时加上判断，如果此时sum > target,无需继续递归，退出当前for循环

代码实现

 List<List<Integer>> result= new ArrayList<>();
	List<Integer> path = new ArrayList<>();
	
	public List<List<Integer>> combinationSum(int[] candidates, int target){

        Arrays.sort(candidates); // 剪枝，先排序，如果sum大于target，那么之后的所有元素都不需要再递归了
		
		backtracking(target, candidates, 0, 0);
		
		return result;
	}
	
	
	public void backtracking(int target, int[]candidates, int sum, int startIndex) {
		
		if(sum == target) {
			result.add(new ArrayList<>(path));
			return;
		}
		
		for(int i = startIndex ; i < candidates.length ; i++) {
			path.add(candidates[i]);
			sum += candidates[i];
			if(sum > target) {
				sum -= candidates[i];
				path.remove(path.size() - 1);
				break;
			}
			backtracking(target, candidates, sum, i);
			sum -= candidates[i];
			path.remove(path.size() - 1);
		}
	}

组合总和2

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
注意：解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8, 输出: [ [1,1,6], [1,2,5], [1,7], [2,6] ]

本题和组合总和类似，但有很多不同点： 1.组合总和中，数组元素不重复，这里重复 2.本题每个数字在每个组合中只能使用一次

难点：有重复元素时，如何做到去重 组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。

回看一下题目，元素在同一个组合内是可以重复的，怎么重复都没事，但两个组合不能相同。所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。

==树层去重，需要先对数组排序，防止漏掉一些可能的情况。如果相邻节点是相同的数，那么前一个节点在进行递归操作时，就已经包含了后一个节点的所有情况，这种情况下，两个节点得到的结果会重复，所以需要对这种情况进行去重==

本题新增了used数组用于判断树层去重，如果此时candidates[i-1]==candidates[i] && !used[i-1] 就需要去重。

为什么used[i-1] == false才进行去重?

说明此时前一个节点已经进行过递归操作，并且进行了回溯。那么此时就不能继续使用当前节点递归

used[i-1] == true 的情况:

说明此时在进行纵向遍历，used[i-1]是上一个递归到的节点，此时仍需要递归得到结果

参数和返回值

参数: 1.used[]: 用来记录同一树枝上的元素是否使用过 2.startIndex: 确认for循环起始位置 3.sum: 当前的总和 4.targetsum: 用于判断的总和 5.candidates[]: 用于得到当前元素

终止条件

sum == target时，当前path加入result,返回

单层递归逻辑

因为去重的操作是在树层上进行的，对应的位置就是在for循环中进行去重操作

去重：判断此时是否需要去重：i > 0 && candidates[i] == candidates[i-1] && !used[i-1],如果是，continue
剪枝: 判断此时sum是否大于target,如果是,break
当前节点加入path
节点值加入sum
当前节点used[i]设置为true
递归，注意不能取自己，startIndex+1
回溯，从path,sum中删除当前节点，used[i]设置为false

剪枝操作

和之前的题目一样，通过sum和target的比较来确定for循环的范围

代码实现

List<List<Integer>> result= new ArrayList<>();
List<Integer> path = new ArrayList<>();

public List<List<Integer>> combinationSum2(int[] candidates, int target) {

    Arrays.sort(candidates);
	//定义一个布尔数组去重
	//具体的用法是看其前一个相邻元素此时的状态
	boolean[] used = new boolean[candidates.length];
	
	backtracking(target, candidates,used, 0, 0);
	
	return result;
    
}

public void backtracking(int target, int[]candidates, boolean[] used, int sum, int startIndex){
	
	if(sum == target) {
		result.add(new ArrayList<>(path));
		return;
	}
	
	for(int i = startIndex ; i < candidates.length ; i++) {
		//for循环剪枝操作
		if(sum + candidates[i]> target) {
			break;
		}
		//如果此时和之前数相等，说明满足树层剪枝的一个条件，如果之前布尔为false,说明此时在树层操作
		if(i > 0 && candidates[i] == candidates[i-1] && !used[i-1]) {
			continue;
		}
		//注意for循环内部顺序要写好，添加写在判断后面，不然添加了退出会出错
		path.add(candidates[i]);
		sum += candidates[i];
		used[i] = true;
		backtracking(target, candidates, used, sum, i + 1);
		sum -= candidates[i];
		used[i] = false;
		path.remove(path.size() - 1);

		
	}

其他

本题也可以不设置used数组，直接通过startIndex来判断去重

List<List<Integer>> result= new ArrayList<>();
List<Integer> path = new ArrayList<>();

public List<List<Integer>> combinationSum2(int[] candidates, int target) {

    Arrays.sort(candidates);
	
	backtracking(target, candidates, 0, 0);
	
	return result;
    
}

public void backtracking(int target, int[]candidates, int sum, int startIndex){
	
	if(sum == target) {
		result.add(new ArrayList<>(path));
		return;
	}
	
	for(int i = startIndex ; i < candidates.length ; i++) {
		//for循环剪枝操作
		if(sum + candidates[i]> target) {
			break;
		}
		//如果此时和之前数相等，说明满足树层剪枝的一个条件
		// i > startIndex : i此时是startIndex之后的节点，跳过同一层使用过的元素
		if(i > startIndex && candidates[i] == candidates[i-1] ) {
			continue;
		}
		//注意for循环内部顺序要写好，添加写在判断后面，不然添加了退出会出错
		path.add(candidates[i]);
		sum += candidates[i];
		backtracking(target, candidates, sum, i + 1);
		sum -= candidates[i];
		path.remove(path.size() - 1);

		
	}
}

分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。
示例 1：
输入：s = “aab” 输出：[[“a”,“a”,“b”],[“aa”,“b”]]

本题的难点: 1.如何切割

使用startIndex作为模拟切割线
每次切割一个字母，结果在切割完毕的叶子节点

2.如何得到每次的分割子数组

startIndex是固定的，i是变化的
所以切割子数组为startIndex - i的左闭右闭区间

3.结束条件

如果此时切割线 >= 字符串长度，说明此时已经切割完毕，到叶子节点

切割问题类似于组合问题：

递归用来纵向遍历，for循环用来横向遍历，切割线（就是图中的红线）切割到字符串的结尾位置，说明找到了一个切割方法。

参数和返回值

一维path存储每次结果，二维result存储总结果
startIndex,用于确定每次切割的位置，重复的位置不能重复切割

终止条件

切割的位置 >= 字符串总长度，说明当前已经切割到末尾

单层递归逻辑

确定当前切割的子串: 从startIndex - i的左闭右闭区间
如果当前切割的字符串是回文子串：
- 把当前子串加入path中
- 递归
- 回溯，删去当前子串
如果不是：
- continue,从下一个位置开始切

判断回文

1.双指针法:

在字符串左右各设置一个指针i,j;for循环比较前后指针对应的字符是否相同，同时i++,j–。如果都相同则为回文子串

2.（优化）动态规划：

和动态规划中判断回文串的方法一样优点：高效地事先一次性计算出, 针对一个字符串s, 它的任何子串是否是回文字串, 然后在我们的回溯函数中直接查询即可, 省去了双指针移动判定这一步骤.

代码实现

回溯+双指针

List<List<String>> result= new ArrayList<>();
List<String> path = new ArrayList<>();

public List<List<String>> partition(String s){
	
	backtracking(0, s);
	
	return result;
}

public void backtracking(int startIndex, String s) {
	
	//说明此时已经切割到了最后一个字符，不能再切割
	if(startIndex >= s.length()) {
		result.add(new ArrayList<>(path));
	}
	
	//startIndex 作为 切割线的位置
	for(int i = startIndex; i < s.length(); i++) {
		//每次切割子串的范围，从startIndex 到 i的左闭右闭区间
		String str = s.substring(startIndex, i+1);
		
		if(check(str)) {
			path.add(str);
			backtracking(i + 1, s);
			path.remove(path.size() - 1);
			
		}else {
			continue;
		}
	}
}

public boolean check(String str) {
	
	int i = 0,j = str.length() - 1;
	
	for(int k = 0 ; k < str.length() ; k++) {
		if(str.charAt(i) != str.charAt(j)) {
			return false;
		}
		i++;
		j--;
	}
	return true;
}

动规+回溯

List<List<String>> result= new ArrayList<>();
List<String> path = new ArrayList<>();
boolean[][] dp;

public List<List<String>> partition(String s){
	
	dp = new boolean[s.length()][s.length()];
	
	check(s.toCharArray());
	
	backtracking(0, s);
	
	return result;
}

public void backtracking(int startIndex, String s) {
	
	//说明此时已经切割到了最后一个字符，不能再切割
	if(startIndex >= s.length()) {
		result.add(new ArrayList<>(path));
	}
	
	//startIndex 作为 切割线的位置
	for(int i = startIndex; i < s.length(); i++) {
		//每次切割子串的范围，从startIndex 到 i的左闭右闭区间
		
		if(dp[startIndex][i]) {
			path.add(s.substring(startIndex, i+1));
			backtracking(i + 1,s );
			path.remove(path.size() - 1);
			
		}else {
			continue;
		}
	}
}

public void check(char[] str) {
	//初始化
	 for (int i = 0; i < str.length; ++i) {
            dp[i][i] = true;
     }
	
	for(int i = str.length - 1 ; i >= 0 ; i--) {
		
		for(int j = i ; j < str.length ; j++) {
			
			if(str[i] == str[j]) {
			
				if(j - i <= 1) {
					dp[i][j] = true;
				}else if(dp[i+1][j-1]) {
					dp[i][j] = true;
				}
			}
		}
	}
}

复原IP地址

有效 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。
例如：“0.1.2.201” 和 “192.168.1.1” 是有效 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是无效 IP 地址。给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 ‘.’ 来形成。你不能重新排序或删除 s 中的任何数字。你可以按任何顺序返回答案。
示例 1：
输入：s = “25525511135” 输出：[“255.255.11.135”,“255.255.111.35”] 示例 2：
输入：s = “0000” 输出：[“0.0.0.0”] 示例 3：
输入：s = “101023” 输出：[“1.0.10.23”,“1.0.102.3”,“10.1.0.23”,“10.10.2.3”,“101.0.2.3”]

难点： 1.如何实现分割，加点 2.startIndex的选取 3.最后一段怎么去掉点

解题思路

==分割问题, 和分割回文串类似。使用startIndex作为当前子串开始分割的位置，for循环中的i作为子串分割结尾。判断[startIndex - i]区间是否满足题目要求，如果满足，在i之后加点，之后递归从下一个位置开始==。==注意递归形参中,startIndex应当为i+2,i+1位置为当前加的点==

参数和返回值:

参数：startIndex, pointSum:用于统计当前点的总数量,同时用于判断终止条件，stringBuilder str:用于在其基础上进行加点，得到结果

递归终止条件:

如果此时pointSum == 3, 说明已经分了四段，此时单独对最终段的内容进行比较，加入result（无需再次加点）

单层递归逻辑:

在for循环中，判断此时的字符子串是否符合要求，符合的话，在子串后加上点，进行递归，查找下一个符合要求的子串

另一种思路:

也可以采用之前的想法，把每段得到的字符串保存下来，最后拼凑成一个完整的答案，传递给result数组作为一个答案。不过这个方法，需要判断好回溯时如何删除加入的字符，还是有点麻烦

注意的点：

1.判断数组:需要注意限制，防止判断的数字大小大于Int类型最大值报错 2.可以使用计算方法，把str每个数字提取出来，计算为数字，之后再进行比较，避免数字过大报错

代码实现

  List<String> result= new ArrayList<>();
	
	public List<String> restoreIpAddresses(String s){
		
		StringBuilder str = new StringBuilder(s);
        //相当剪枝
        if(s.length() > 12 || s.length() < 4)return result;
		
		backtracking(0, str, 0);
			
		return result;
	}
	
	
	public void backtracking(int startIndex, StringBuilder s, int pointSum) {
		
		if(pointSum == 3) {
			if(check(s.toString(), startIndex, s.length() - 1)) {
				result.add(s.toString());
			}
			return;
		}
	
		for(int i = startIndex;i < s.length() ; i++) {
			//保证每次处理的数字大小
			if(i - startIndex + 1> 3)break;
            //判断是否符合要求
			if(!check(s.toString(), startIndex , i))break;
			//插入点
			s.insert(i+1,".");
			pointSum+=1;
			//注意，递归是从i+2开始，因为要考虑插入的点
			backtracking(i+2, s, pointSum);
			//回溯，删除点
			pointSum-=1;
			s.deleteCharAt(i+1);
			
		}
		
		
	}
	
	public boolean check(String str, int startIndex, int i) {
		//异常情况
		if(startIndex > i)return false;
		
		//头数字为0的情况
		if(str.charAt(startIndex) == '0' && startIndex != i)return false;
		//不符合要求的情况
		if(Integer.parseInt(str.substring(startIndex, i + 1)) < 0 ||Integer.parseInt(str.substring(startIndex, i + 1)) > 255)return false;
		
		return true;
		
	}

子集

给你一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。
解集不能包含重复的子集。你可以按任意顺序返回解集。
示例 1：
输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 示例 2：
输入：nums = [0] 输出：[[],[0]]

解题思路

和分割,组合类型的题目不同，画出树形结构，发现答案是并不是只是根节点，而是树上所有的节点。所有添加答案的时候，没有判断条件，而是每次递归得到的都需要添加。

子集也是一种组合问题，因为它的集合是无序的，子集{1,2} 和子集{2,1}是一样的。

那么既然是无序，取过的元素不会重复取，写回溯算法的时候，for就要从startIndex开始，而不是从0开始。

参数和返回值

1.nums数组: 用于寻找得到结果 2.startIndex: 确定每次开始位置，因为同个元素不能重复选择

终止条件

可有可无，可以是当前startIndex >= nums.length时返回，也可以不写，因为每次递归，startIndex都在改变，所以不会死循环。

单层递归逻辑

把当前nums[i]加入path,递归，之后回溯从path中移除nums[i]

代码实现

 List<List<Integer>> result= new ArrayList<>();
	List<Integer> path = new ArrayList<>();
	
	public List<List<Integer>> subsets(int[] nums){
		
		
		backtracking(0,nums);
			
		return result;
	}
	
	
	public void backtracking(int startIndex, int[] nums) {
		
		result.add(new ArrayList<>(path));

        if (startIndex >= nums.size()) {
            return;
        }
		
		for(int i = startIndex; i < nums.length ; i++) {
			
			path.add(nums[i]);
			backtracking(i + 1, nums);
			path.remove(path.size() - 1);
			
		}
		
	}

子集Ⅱ

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集不能包含重复的子集。返回的解集中，子集可以按任意顺序排列。
示例 1：
输入：nums = [1,2,2] 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]] 示例 2：
输入：nums = [0] 输出：[[],[0]]

解题思路

和组合总和Ⅱ类似，由于不能包含重复的子集，所以需要去重操作

在了解组合总和Ⅱ如何实现去重之后，很简单

代码实现

List<List<Integer>> result= new ArrayList<>();
	List<Integer> path = new ArrayList<>();
	
	public List<List<Integer>> subsetsWithDup(int[] nums){
		
		//用于去重
		boolean[] used = new boolean[nums.length];

        //排序,防止漏掉其他情况
		Arrays.sort(nums);
		
		backtracking(0,nums, used);
			
		return result;
	}
	
	
	public void backtracking(int startIndex, int[] nums, boolean[] used) {
		
		result.add(new ArrayList<>(path));
		
		for(int i = startIndex; i < nums.length ; i++) {
			
			if(i > 0 && nums[i-1] == nums[i] && !used[i-1])continue;
			
			path.add(nums[i]);
			used[i] = true;
			backtracking(i + 1, nums,used);
			path.remove(path.size() - 1);
			used[i] = false;
			
		}
		
	}

非递减子序列

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中至少有两个元素。你可以按任意顺序返回答案。
数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
示例 1：
输入：nums = [4,6,7,7] 输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]] 示例 2：
输入：nums = [4,4,3,2,1] 输出：[[4,4]]

根据题目，需要求不同的递增子序列，且至少有两个元素。那么去重的操作就是必须的

==和子集Ⅱ不同的点：==

子集Ⅱ求所有可能的子集，不需要满足在原数组上的递增子序列，所以去重可以采用排序+used数组的方式
本题需要在原数组的基础上去重，不能进行排序，所以不能使用之前的方式进行去重，比如:6,7,6这种情况。

参数:

startIndex : 避免取到自身
nums:访问原数组里的元素

终止条件:

因为题目提到子序列中至少两个元素:

if(path.size() > 1) {
			result.add(new ArrayList<>(path));
		}

单层递归逻辑:

在图中可以看出，同一父节点下的同层上使用过的元素就不能再使用了

HashSet<Integer> hs = new HashSet<>();
		
for(int i = startIndex; i < nums.length ; i++) {
	
	if(path.size() > 0 && path.get(path.size() - 1) > nums[i] ||
			hs.contains(nums[i])) {
		continue;
	}
	
	path.add(nums[i]);
	hs.add(nums[i]);
	backtracking(i + 1, nums);
	path.remove(path.size() - 1);
}

==hs的作用：去重，得到当前层元素的集合==
==回溯部分，为什么不从hs中移除nums[i]:因为hs只记录当前层去重后的元素，是否可重复使用==

优化：

也可以通过数组作哈希映射，提高效率

    int[] used = new int[201];
    for (int i = start; i < nums.length; i++) {
        if (!path.isEmpty() && nums[i] < path.get(path.size() - 1) ||
                (used[nums[i] + 100] == 1)) continue;
        used[nums[i] + 100] = 1;
        path.add(nums[i]);
        backtracking(nums, i + 1);
        path.remove(path.size() - 1);

代码实现

List<List<Integer>> result= new ArrayList<>();
List<Integer> path = new ArrayList<>();

public List<List<Integer>> findSubsequences(int[] nums){
	
	//用于去重
//		boolean[] used = new boolean[nums.length];
	
	//排序
//		Arrays.sort(nums);
	
	backtracking(0,nums);
		
	return result;
}


public void backtracking(int startIndex, int[] nums) {
	
	if(path.size() > 1) {
		result.add(new ArrayList<>(path));
	}
	//利用hashset实现本层结果的去重
    //因为需要不同的递增子序列
    //于之前的不同点：1.不能排序
    //2.不能排序，导致去重不能使用原来方法，如: 6,7,6 这种情况
	HashSet<Integer> hs = new HashSet<>();
	
	for(int i = startIndex; i < nums.length ; i++) {
		
		if(path.size() > 0 && path.get(path.size() - 1) > nums[i] ||
				hs.contains(nums[i])) {
			continue;
		}
		
		path.add(nums[i]);
		hs.add(nums[i]);
		backtracking(i + 1, nums);
		path.remove(path.size() - 1);

	}
}

全排列

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

==和组合问题不同,排列问题[1,2]和[2,1]看做不同的答案，所以不需要startIndex来记录起始位置。但是需要使用used数组来记录当前路径使用过的元素。==

参数和返回值:

nums数组：用于得到数组中的元素
used数组：记录当前路径下对应的nums[i]元素有没有使用过

终止条件:

如果此时path.size()和nums.length长度相同，说明找到一个答案，添加并返回这里不能固定死

单层递归逻辑:

如果此时nums中的数字已经使用过，那么直接跳过递归，从下一个位置开始尝试

for(int i = 0; i < nums.length ; i++) {
			
			if(used[i]) {
				continue;
			}
			
			path.add(nums[i]);
			used[i] = true;
			backtracking(nums , used);
			path.removeLast();
			used[i] = false;
			
		}

注意要点

for循环：横向遍历递归：纵向遍历

used数组虽然回溯后恢复原状，但是for循环已经循环的次数是固定的，所以在之后的循环中，才能拿到前面的元素。

代码实现

List<List<Integer>> result= new ArrayList<>();

//注意此时的路径是LinkedList，方便取出元素
LinkedList<Integer> path = new LinkedList<>();
 
public List<List<Integer>> permute(int[] nums){
	
	boolean[] used = new boolean[nums.length];
	
	backtracking(0,nums,used);
		
	return result;
}

public void backtracking(int depth, int[] nums, boolean[]used) {
	
	//终止条件，如果此时path的元素个数和nums数组中相等，说明找到一个答案
	if(path.size() == nums.length) {
		result.add(new ArrayList<>(path));
		return;
	}
	
	
	for(int i = 0; i < nums.length ; i++) {
		
		if(used[i]) {
			continue;
		}
		
		path.add(nums[i]);
		used[i] = true;
		backtracking(depth + 1, nums , used);
		path.removeLast();
		used[i] = false;
		
	}
	
}

全排列Ⅱ

给定一个可包含重复数字的序列 nums ，按任意顺序返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2] 输出： [[1,1,2], [1,2,1], [2,1,1]] 示例 2：
输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

根据题目，包含重复数字的序列 nums ，按任意顺序返回所有不重复的全排列，可知，这题是求全排列，但是需要去重

去重方法： 组合总和Ⅱ中，目的是找出所有不重复的组合，没有序列上的要求，所以通过排序，再使用used数组来判断是否去重。

递增子序列中，目的是找到所有该数组中不同的递增子序列。有序列上的要求，所以不能排序，使用Hashset进行去重

对于本题来说，找到所有的全排列，数组中数字的顺序不影响，所以可以使用排序+used数组的方式进行去重，也可以使用set进行去重

参数和返回值

nums数组
used数组

递归终止条件:

如果此时path.size == nums.length,说明找到一个结果

单层递归逻辑:

//满足去重条件，略过
            //used[i-1] :树枝去重
            //!used[i-1]:树层去重，效率更高
			if(i > 0 && nums[i-1] == nums[i] && !used[i-1]) {
				continue;
			}
			
            //排列，略过当前元素已经使用过的情况
			if(!used[i]) {
				path.add(nums[i]);
				used[i] = true;
				backtracking(nums , used);
				path.removeLast();
				used[i] = false;
			}

满足去重条件，continue;满足全排列的条件（当前数字未使用），进行递归回溯操作。

拓展

在去重的时候：

if(i > 0 && nums[i-1] == nums[i] && !used[i-1]) {
			continue;
		}

和

if(i > 0 && nums[i-1] == nums[i] && used[i-1]) {
			continue;
		}

都能通过。其中!used[i-1]说明此时在进行树层去重，used[i-1]说明此时在进行树枝去重。 ==说明对于排列问题，树枝去重和树层去重两种方式都能得到正确答案== 但是树层去重的效率更高

例：对于[1,1,1]进行树层去重和树枝去重：树层去重

树枝去重

两种去重方法的比较

1.求子集，排列问题如果使用set来去重，需要先对数组排序，防止出现重复的情况

2.使用set去重，在时间复杂度和空间复杂度上都比用used数组高。如果使用set去重，空间复杂度就变成了O(n^2)，因为每一层递归都有一个set集合，系统栈空间是n，每一个空间都有set集合。used数组可是全局变量，每层与每层之间公用一个used数组，所以空间复杂度是O(n + n)，最终空间复杂度还是O(n)。

N皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个不同的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
示例 1：
输入：n = 4 输出：[[".Q..","…Q",“Q…”,"..Q."],["..Q.",“Q…”,"…Q",".Q.."]] 解释：如上图所示，4 皇后问题存在两个不同的解法。示例 2：
输入：n = 1 输出：[[“Q”]]

n皇后问题属于回溯算法中的棋盘问题。每一行只能放一个皇后，可以把放置皇后的过程抽象为树结构。可以发现，答案在叶子节点的位置得到。

参数和返回值

参数：二维的char棋盘chessboard, 棋盘大小n, 当前深度，用于判断是否达到叶子节点。

终止条件

当前深度 == 棋盘大小n，说明深度达到叶子节点，把当前chessboard中的结果加入result中返回

单层递归逻辑

for(int i = 0 ; i< n ; i++) {
			
			if(check(i, depth, bishop)) {
				
				bishop[depth][i] = 'Q';
				backtracking(n, depth+1, bishop);
				bishop[depth][i] = '.';
						
			}
			
		}

for循环遍历当前行的所有列位置，检测位置，若符合要求，在该位置进行递归回溯操作。

检测

public boolean check(int pos , int depth, char[][] bishop) {

		for(int i = depth - 1; i >= 0 ; i--) {
			if(bishop[i][pos] == 'Q')return false;
		}
		
		for(int i = depth - 1, j = pos + 1; i >= 0 && j < bishop[i].length ; i--,j++) {
			if(bishop[i][j] == 'Q')return false;
		}
		
		for(int i = depth - 1, j = pos - 1; i >= 0 && j >=0; i--,j--) {
			if(bishop[i][j] == 'Q')return false;
		}
		
		return true;
	}

需要检测当前象棋的列；45°，135°斜线位置不能有其他棋子。不需要检测行，因为一行只有一个。

public boolean check(int pos , int depth, char[][] bishop) {
		
		
		
		for(int i = depth - 1; i >= 0 ; i--) {
			if(bishop[i][pos] == 'Q')return false;
		}
		
		
		for(int i = depth - 1, j = pos + 1; i >= 0 && j < bishop[i].length ; i--,j++) {
			if(bishop[i][j] == 'Q')return false;
		}
		
		for(int i = depth - 1, j = pos - 1; i >= 0 && j >=0; i--,j--) {
			if(bishop[i][j] == 'Q')return false;
		}
		
		
		
		return true;
		
	}

解数独

编写一个程序，通过填充空格来解决数独问题。
数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）数独部分空格内已填入了数字，空白格用 ‘.’ 表示。
示例 1：
输入：board = [[“5”,“3”,".",".",“7”,".",".",".","."],[“6”,".",".",“1”,“9”,“5”,".",".","."],[".",“9”,“8”,".",".",".",".",“6”,"."],[“8”,".",".",".",“6”,".",".",".",“3”],[“4”,".",".",“8”,".",“3”,".",".",“1”],[“7”,".",".",".",“2”,".",".",".",“6”],[".",“6”,".",".",".",".",“2”,“8”,"."],[".",".",".",“4”,“1”,“9”,".",".",“5”],[".",".",".",".",“8”,".",".",“7”,“9”]] 输出：[[“5”,“3”,“4”,“6”,“7”,“8”,“9”,“1”,“2”],[“6”,“7”,“2”,“1”,“9”,“5”,“3”,“4”,“8”],[“1”,“9”,“8”,“3”,“4”,“2”,“5”,“6”,“7”],[“8”,“5”,“9”,“7”,“6”,“1”,“4”,“2”,“3”],[“4”,“2”,“6”,“8”,“5”,“3”,“7”,“9”,“1”],[“7”,“1”,“3”,“9”,“2”,“4”,“8”,“5”,“6”],[“9”,“6”,“1”,“5”,“3”,“7”,“2”,“8”,“4”],[“2”,“8”,“7”,“4”,“1”,“9”,“6”,“3”,“5”],[“3”,“4”,“5”,“2”,“8”,“6”,“1”,“7”,“9”]] 解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

本题和N皇后一样都属于棋盘问题，但是区别在于: 1.N皇后问题，每行只需要一个皇后，用单层for循环就可以找到合适的位置；而该题每行每个空位都需要填一个数字。所以，本题需要使用双层for循环，二维数组的写法,解数独的树形结构要比N皇后更宽更深。 2.本题不需要找出所有的结果，而是找到一个结果即可，返回值不再是void,而是boolean

参数和返回值

参数：棋盘(不需要其他，因为只需找到一个结果) 返回值： boolean

递归终止条件

无需终止条件，而是找到可能的叶子节点就立即返回。

不用终止条件会不会死循环？
- 递归的下一层的棋盘一定比上一层的棋盘多一个数，等数填满了棋盘自然就终止（填满当然好了，说明找到结果了），所以不需要终止条件

单层递归逻辑

//二维递归,和n皇后一行只确定一个位置不同，此时一行的每个位置都需要确定
//所以使用双层for循环，确定位置后，再从1~9中寻找合适的数字
for(int i = 0 ; i < board.length ; i++) {
	
	for(int j = 0 ; j < board[0].length; j++) {
		//为数字，跳过
		if(board[i][j] != '.')continue;
		//每个位置从1~9中寻找合适的数字
		for(char k ='1'; k <= '9'; k++) {
			//检测满足题目规则
			if(check(i, j, k,board)) {
				
				board[i][j] = k;
				boolean result = backtracking(board);
				if(result)return true; // 如果找到合适一组立刻返回
				board[i][j] = '.';
				
			}
		}
		return false; //9个数都试过了，不符合条件，返回false
	}
}
return true; // 遍历完没有返回false，说明找到了合适棋盘位置

1.一个for循环遍历行，一个for循环遍历列，确定每一个位置

2.如果当前不为空就跳过

3.如果检测当前符合填入数字的条件，就遍历1~9，递归查找放9个数字的可能性

4.return false: 如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解那么会直接返回，这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去

5.return true:如果遍历结束没有返回false,说明找到了符合的位置，返回true

6.if中的return true: 如果回溯结果为true,说明找到合适结果，直接返回

判断棋盘是否合法

public boolean check(int rowPos , int colPos,char k, char[][] board) {
		
		for(int i = 0 ; i < board.length ; i++) {//行
			if(board[rowPos][i] == k) {
				return false;
			}
		}
		
		for(int j = 0 ; j < board[0].length; j++) {//列
			if(board[j][colPos] == k) {
				return false;
			}
		}
		
		int row = (rowPos / 3)* 3; //确定区间的起始位置
		int col = (colPos / 3)* 3;
		
		for(int i = row ; i < row + 3; i++) {
			
			for(int j = col ;  j < col + 3 ; j++) {
				
				if(board[i][j] == k) {
					return false;
				}
				
			}
			
		}
		return true;
	}

如何确定属于9宫格中哪个位置: 棋盘的划分: 这是因为整个 9x9 的棋盘按照九宫格划分，可以看成由 3X3 的子区域组成，每个子区域是 3X3 的小矩阵。通过整除运算和乘法，我们可以快速确定一个单元格所在子区域的左上角（起点）的坐标。

分析

棋盘的划分:
- 行号范围为 \(0\) 到 \(8\)，列号范围也为 \(0\) 到 \(8\)。
- 棋盘按照 3X3 的子区域划分，有 \(9\) 个子区域。
- 每个子区域可以用它的左上角坐标（起点）唯一确定，例如：
  - 左上角的子区域起点是 \((0, 0)\)。
  - 中间的子区域起点是 \((3, 3)\)。
  - 右下角的子区域起点是 \((6, 6)\)。
行号和列号对应子区域编号:
- 对于任意单元格的行号 row 和列号 col，它所在的子区域编号可以通过整除 3 得到：
  - row / 3 表示它是第几个子区域的行编号。
  - col / 3 表示它是第几个子区域的列编号。
起点坐标的计算:
- 子区域的行编号为 row / 3，要得到该子区域的起点行号，可以将其乘以 \(3\)：
  - 起点行号 = (row / 3) * 3。
- 子区域的列编号为 col / 3，要得到该子区域的起点列号，可以将其乘以 \(3\)：
  - 起点列号 = (col / 3) * 3。

举例说明

假设单元格坐标为 (row, col) = (4, 7)：

确定子区域编号:
- row / 3 = 4 / 3 = 1（取整，表示它位于第 1 行的子区域）。
- col / 3 = 7 / 3 = 2（取整，表示它位于第 2 列的子区域）。
计算子区域的起点:
- 起点行号：\((row / 3) * 3 = 1 * 3 = 3\)。
- 起点列号：\((col / 3) * 3 = 2 * 3 = 6\)。
结果:
- 单元格 \((4, 7)\) 所在的子区域起点是 \((3, 6)\)。

为什么有效？

规律性:
- 子区域的起点总是位于行号和列号能被 \(3\) 整除的位置：例如 \(0, 3, 6\)。
- 将行号和列号除以 \(3\) 后得到的商，唯一标识了单元格所在的子区域编号。
通用性:
- 这种方法适用于任何 \(n \times n\) 棋盘（只要 \(n\) 能整除子区域的大小），不仅仅是 \(9 \times 9\)。

可视化理解

将棋盘按照九宫格划分，每个子区域的起点如下：

(0, 0)  (0, 3)  (0, 6)
(3, 0)  (3, 3)  (3, 6)
(6, 0)  (6, 3)  (6, 6)

假设单元格为 \((4, 7)\)，它在：

第 2 行的子区域（row / 3 = 1）。
第 3 列的子区域（col / 3 = 2）。

所以起点为 \((3, 6)\)。