回溯类
2578字约9分钟
2024-10-20
前言
回溯类题目
排列
组合与排列都是组合数学中的基本概念。
排列是指从 n 个不同元素中取出 m（m ≤ n）个元素，按照一定的顺序「排成一列」的方法数目。这里的关键是“顺序”很重要，不同的排列顺序被认为是不同的结果。
举个例子：从 1、2、3、4 中取出 4 个元素进行排列，由于排列强调顺序，所以 {1,2,3,4} 和 {1,3,2,4} 是两个不同的排列。
相关公式：
- 如果从 n 个不同元素中取出全部 n 个元素进行排列，则排列数为 P(n,n)=n!
- 如果从 n 个不同元素中取出 m 个元素进行排列，则排列数为 P(n,m)=(n−m)!n!。
排列类问题，一般就是给你一个数组，返回这个数组的全排列，然后这个数组有可能有一些重复的元素，所以还要看需不需要去重。
全排列
这里给的数组是没有重复元素的，所以也就不要求去重，还是比较简单的，使用一个额外的 used 数组表示 i 位置是否已经选择过，如果选择过就跳过该位置。
import java.util.*;
public class Solution {
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> permute(int[] nums) {
boolean[] used = new boolean[nums.length];
backtracking(nums, used);
return res;
}
private void backtracking(int[] nums, boolean[] used) {
if (path.size() == nums.length) {
res.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) {
continue;
}
used[i] = true;
path.add(nums[i]);
backtracking(nums, used);
path.removeLast();
used[i] = false;
}
}
}对于这种无重复数组的全排列还有另一种解法，就是交换元素，如下：
import java.util.*;
public class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
backtracking(new ArrayList<>(Arrays.stream(nums).boxed().toList()), 0);
return res;
}
private void backtracking(List<Integer> nums, int pos) {
if (pos == nums.size()) {
res.add(new ArrayList<>(nums));
return;
}
for (int i = pos; i < nums.size(); i++) {
swap(nums, i, pos);
backtracking(nums, pos + 1);
swap(nums, i, pos);
}
}
private void swap(List<Integer> nums, int i, int j) {
int tmp = nums.get(i);
nums.set(i, nums.get(j));
nums.set(j, tmp);
}
}全排列 II
全排列 II 这道题目给出的数组中就会出现重复的元素，所以我们还需要在回溯的过程中进行去重。
去重的关键是 used 数组，如果 used[i - 1] = true 表示同一树枝 nums[i - 1] 使用过，used[i - 1] = false 表示同一树层 nums[i - 1] 使用过。
—— 代码随想录
我的理解是，我们在向下一个位置继续递归之前，会将 used[i] 置为 true，所以当来到下一层递归时，used[i - 1] 就为 true，这就表示是从上一层递归来的，而我们也说，递归是纵向的，所以是树枝，既然 used[i - 1] 为 true 是树枝了，那为 false 就是树层了。
另外一定要记住，nums 数组要提前排好序，这样相同的元素才是挨着的。
import java.util.*;
public class Solution {
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
boolean[] used = new boolean[nums.length];
Arrays.sort(nums);
backtracking(nums, used);
return res;
}
private void backtracking(int[] nums, boolean[] used) {
if (path.size() == nums.length) {
res.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
// 选择过 相邻的元素是相同的，并且是同一树层
if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
continue;
}
used[i] = true;
path.add(nums[i]);
backtracking(nums, used);
path.removeLast();
used[i] = false;
}
}
}组合
组合是指从 n 个不同元素中取出 m（m ≤ n）个元素并「组成集合」的方法数目。这里的关键是“顺序”不重要，不论如何排列这 m 个元素都被认为是同一种选择方法。
举个例子：从 1、2、3、4 中取出 4 个元素进行组合，由于组合不强调顺序，所以 {1,2,3,4} 和 {1,3,2,4} 是相同的组合。
相关公式：
- 如果是从 n 个不同元素中取出 m 个元素进行组合，则组合数为 C(n,m)=m!(n−m)!n!。
组合
注意有一个优化剪枝的点，在递归每一层的 for 循环的起始位置之后的元素个数已经不足 k 个，后续是无法选出 k 个元素的，所以无需继续搜索。
import java.util.*;
public class Solution {
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combine(int n, int k) {
backtracking(n, k, 1);
return res;
}
private void backtracking(int n, int k, int pos) {
if (path.size() == k) {
res.add(new ArrayList<>(path));
return;
}
// 剪枝优化如下：
// path.size() ==> 已经选了
// k - path.size() ==> 还需要选
// n - i - 1 ==> 还剩的数
// n - i - 1 <= k - path.size() ==> 剩下的数不够了则提前退出循环
// 整理 ==> i <= n - (k - path.size()) + 1
for (int i = pos; i <= n - (k - path.size()) + 1; i++) {
path.add(i);
backtracking(n, k, i + 1);
path.removeLast();
}
}
}电话号码的字母组合
很简单，没有什么特别需要关注的点。
import java.util.*;
public class Solution {
String[] MAPPING = {
"", "",
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz"
};
List<String> res = new ArrayList<>();
StringBuilder path = new StringBuilder();
public List<String> letterCombinations(String digits) {
if (digits.isEmpty()) {
return res;
}
backtracking(digits.toCharArray(), 0);
return res;
}
private void backtracking(char[] chars, int pos) {
if (path.length() == chars.length) {
res.add(path.toString());
return;
}
for (int i = 0; i < MAPPING[chars[pos] - '0'].length(); i++) {
path.append(MAPPING[chars[pos] - '0'].charAt(i));
backtracking(chars, pos + 1);
path.deleteCharAt(path.length() - 1);
}
}
}组合总和
import java.util.*;
public class Solution {
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
backtracking(candidates, target, 0);
return res;
}
private void backtracking(int[] candidates, int target, int pos) {
if (target <= 0) {
if (target == 0) {
res.add(new ArrayList<>(path));
}
return;
}
for (int i = pos; i < candidates.length; i++) {
path.add(candidates[i]);
// 由于同一个位置的数可以重复使用，所以仍然从 i 开始
backtracking(candidates, target - candidates[i], i);
path.removeLast();
}
}
}这里也存在一个剪枝优化，如果 target 减去当前的数之后就已经小于 0 了，其实就没有必要进入下一层递归，所以我们可以提前结束 for 循环。
但是，这里需要额外对 nums 数组升序排序，否则前面较大的数可能导致 for 循环提前退出，但是后面其实还有合适的解。
import java.util.*;
public class Solution {
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
backtracking(candidates, target, 0);
return res;
}
private void backtracking(int[] candidates, int target, int pos) {
if (target == 0) {
res.add(new ArrayList<>(path));
return;
}
for (int i = pos; i < candidates.length && target - candidates[i] >= 0; i++) {
path.add(candidates[i]);
// 由于同一个位置的数可以重复使用，所以仍然从 i 开始
backtracking(candidates, target - candidates[i], i);
path.removeLast();
}
}
}组合总和 II
这里题目的新要求是每个数字只能使用一次，同时由于给定的数组是有重复的，所以最后还需要去重。
这里去重也是基于全排列 II 中的去重方式，使用 used 数组进行去重，used[i - 1] = false 表示同一树层选择过！！！
还有注意，先排序，保证相同的元素是挨着的。
import java.util.*;
public class Solution {
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
boolean[] used = new boolean[candidates.length];
backtracking(candidates, target, 0, used);
return res;
}
private void backtracking(int[] candidates, int target, int pos, boolean[] used) {
if (target == 0) {
res.add(new ArrayList<>(path));
return;
}
for (int i = pos; i < candidates.length && target - candidates[i] >= 0; i++) {
if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) {
continue;
}
used[i] = true;
path.add(candidates[i]);
backtracking(candidates, target - candidates[i], i + 1, used);
path.removeLast();
used[i] = false;
}
}
}组合总和 III
这题就很简单了，你可以使用 used 数组去重，也可以基于 pos 位置去重。
下面是基于 pos 位置去重的解法。
import java.util.*;
public class Solution {
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
backtracking(k, n, 1);
return res;
}
private void backtracking(int k, int n, int pos) {
if (path.size() == k) {
if (n == 0) {
res.add(new ArrayList<>(path));
}
return;
}
for (int i = pos; i <= 9; i++) {
path.add(i);
backtracking(k, n - i, i + 1);
path.removeLast();
}
}
}分割
分割回文串
首先要解决的问题就是如何高效的求一个子串是否是回文串，这道题目可以实时求，也可以先将 dp 数组预处理出来。
这里我们就简单起见，实时求。
import java.util.*;
public class Solution {
List<List<String>> res = new ArrayList<>();
LinkedList<String> path = new LinkedList<>();
public List<List<String>> partition(String s) {
char[] chars = s.toCharArray();
backtracking(chars, 0);
return res;
}
private void backtracking(char[] chars, int start) {
if (start == chars.length) {
res.add(new ArrayList<>(path));
return;
}
for (int i = start; i < chars.length; i++) {
if (!isPalindrome(chars, start, i)) {
continue;
}
path.add(new String(chars, start, i - start + 1));
backtracking(chars, i + 1);
path.removeLast();
}
}
// chars[i...j] 是否是回文串
public boolean isPalindrome(char[] chars, int i, int j) {
while (i <= j) {
if (chars[i] != chars[j]) {
return false;
}
i++;
j--;
}
return true;
}
}复原 IP 地址
老实说，这道题挺扣细节的，有点恶心。
import java.util.*;
class Solution {
List<String> res = new ArrayList<>();
StringBuilder path = new StringBuilder();
public List<String> restoreIpAddresses(String s) {
if (s.length() > 12) {
return res;
}
char[] chars = s.toCharArray();
backtracking(chars, 0, 0);
return res;
}
private void backtracking(char[] chars, int start, int seg) {
if (start == chars.length || seg == 4) {
if (start == chars.length && seg == 4) {
res.add(path.toString());
}
return;
}
for (int i = start; i < chars.length; i++) {
if (!check(chars, start, i)) {
continue;
}
path.append(new String(chars, start, i - start + 1));
// ip 段数量小于 3 才加点
if (seg < 3) {
path.append('.');
}
backtracking(chars, i + 1, seg + 1);
// 删除当前 path 的最后一个 ip 段，注意考虑点的数量
path.delete(start + seg, i + seg + 2);
}
}
// chars[i...j] 是否满足网段要求
private boolean check(char[] chars, int i, int j) {
// 前导 0 超出 3 位
if ((i < j && chars[i] == '0') || j - i >= 3) {
return false;
}
int num = 0;
for (; i <= j; i++) {
num = num * 10 + chars[i] - '0';
}
return num >= 0 && num <= 255;
}
}子集
本质上来说，子集问题就是在递归展开时，收集每一个节点的信息，而不是只在叶子节点收集。
子集
import java.util.*;
public class Solution {
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.subsets(new int[]{1, 2, 3}));
}
public List<List<Integer>> subsets(int[] nums) {
backtracking(nums, 0);
return res;
}
private void backtracking(int[] nums, int pos) {
res.add(new ArrayList<>(path));
for (int i = pos; i < nums.length; i++) {
path.add(nums[i]);
backtracking(nums, i + 1);
path.removeLast();
}
}
}子集 II
老样子的去重问题了，先排序，然后使用 used 数组去重。
public class Solution {
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
boolean[] used = new boolean[nums.length];
Arrays.sort(nums);
backtracking(nums, 0, used);
return res;
}
private void backtracking(int[] nums, int pos, boolean[] used) {
res.add(new ArrayList<>(path));
for (int i = pos; i < nums.length; i++) {
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue;
}
used[i] = true;
path.add(nums[i]);
backtracking(nums, i + 1, used);
path.removeLast();
used[i] = false;
}
}
}