题型：回溯|睡懒觉的随想录

回溯入门

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

本题是一个非常经典的回溯问题，每个数字有对应的可选字符，我们从第 1 个数字开始枚举其可以选择的所有字符，然后递归到第 2 个数字继续枚举，直到枚举完所有数字保存答案。

String[] MAPPING = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
List<String> ans = new ArrayList<>();
StringBuilder sb = new StringBuilder();
char[] digits;

public List<String> letterCombinations(String digits) {
    int n = digits.length();
    if (n == 0) {
        return ans;
    }
    this.digits = digits.toCharArray();
    dfs(0);
    return ans;
}

private void dfs(int i) {
    // 枚举完所有数字，结束递归，保存答案
    if (i == digits.length) {
        ans.add(sb.toString());
        return;
    }
    // 当前数字
    int num = digits[i] - '0';
    // 枚举当前数字可能选择的字符
    for (char c : MAPPING[num].toCharArray()) {
        sb.append(c); // 选择字符 c
        dfs(i + 1); // 递归下一个位置
        sb.deleteCharAt(sb.length() - 1); // 恢复现场
    }
}

一、子集型回溯

有「选或不选」和「枚举选哪个」两种写法。

「选或者不选」的结果都位于「叶节点」
而「枚举选哪个」的结果位于「每个节点」

78 子集

给你一个整数数组 nums ，数组中的元素「互不相同」。返回该数组所有可能的子集（幂集）。
解集「不能」包含重复的子集。你可以按「任意顺序」返回解集。

从输入的角度考虑每个 nums[i] 是选还是不选，由此组合出所有子集。

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

public List<List<Integer>> subsets(int[] nums) {
    dfs(nums, 0);
    return ans;
}

private void dfs(int[] nums, int i){
    if (i == nums.length){
        ans.add(new ArrayList<>(path));
        return;
    }
    // 选
    path.add(nums[i]);
    dfs(nums, i + 1);
    path.removeLast();
    // 不选
    dfs(nums, i + 1);
}

2597. 美丽子集的数目

可以通过回溯实现，在选的过程中判断是否可以选。

Map<Integer, Integer> cnt = new HashMap<>();
int ans = -1; // 排除空集
int k;

public int beautifulSubsets(int[] nums, int k) {
    this.k = k;
    dfs(nums, 0);
    return ans;
}

public void dfs(int[] nums, int i) {
    if (i == nums.length) {
        ans++;
        return;
    }
    // 不选
    dfs(nums, i + 1);
    // 判断是否可以选
    int x = nums[i];
    if (cnt.getOrDefault(x + k, 0) == 0 && cnt.getOrDefault(x - k, 0) == 0) {
        cnt.merge(nums[i], 1, Integer::sum); // 选
        dfs(nums, i + 1);
        cnt.merge(nums[i], -1, Integer::sum); // 恢复现场
    }
}

枚举选哪个的写法：

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

public List<List<Integer>> subsets(int[] nums) {
    dfs(nums, 0);
    return ans;
}

private void dfs(int[] nums, int i){
    ans.add(new ArrayList<>(path));
    // 枚举选择的数字
    for (int j = i; j < nums.length; j++){
        path.add(nums[j]);
        dfs(nums, j + 1);
        path.removeLast();
    }
}

39. 组合总和

给你一个「无重复元素」的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有「不同组合」，并以列表形式返回。你可以按「任意顺序」返回这些组合。
candidates 中的「同一个」数字可以「无限制重复被选取」。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。

这个思路和完全背包类似。具体使用 dfs(i, target) 来回溯，设当前枚举到 candidates[i]，剩余要选的元素之和为 target，按照选或不选讨论：

选，递归到 dfs(i, target-candidates[i])， i 不变，表示可以重复选。
不选，递归到 dfs(i+1,target)。

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

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

public void dfs(int[] candidates, int i, int target){
    // 找到合法组合
    if (target == 0){
        ans.add(new ArrayList<>(path));
        return;
    }
    // 剪枝优化：如果当前元素大于 target，可以直接退出
    if (i == candidates.length || target < candidates[i]){
        return;
    }
    // 选
    path.add(candidates[i]);
    dfs(candidates, i, target - candidates[i]);
    path.removeLast();
    // 不选
    dfs(candidates, i + 1, target);
}

40. 组合总和 II

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
注意：解集不能包含重复的组合。

本题思路和【组合总和】相同，不同点在于本题需要去重，只需要在「不选」的时候跳过所有后续等于当前元素的数。

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

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    Arrays.sort(candidates);
    dfs(candidates, 0, target);
    return ans;
}

public void dfs(int[] candidates, int i, int target){
    if (target == 0){
        ans.add(new ArrayList<>(path));
        return;
    }
    if (i == candidates.length || target < candidates[i]){
        return;
    }
    // 选
    path.add(candidates[i]);
    dfs(candidates, i + 1, target - candidates[i]);
    path.removeLast();  // 恢复现场
    // 不选，则跳过所有相同的元素，避免重复
    int j = i + 1;
    while (j < candidates.length && candidates[j] == candidates[i]){
        j++;
    }
    dfs(candidates, j, target);
}

二、划分型回溯

131. 分割回文串

三、组合型回溯

77. 组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按任何顺序返回答案。

从 n 遍历到 1，判断当前数字选或不选即可。当已选的数字数量等于 k 时，保存答案，结束递归。

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

public List<List<Integer>> combine(int n, int k) {
    dfs(n, k);
    return ans;
}

public void dfs(int i, int k) {
    // 还需要选 d 个数字
    int d = k - path.size();
    // 选好了
    if (d == 0){
        ans.add(new ArrayList<>(path));
        return;
    }
    // 剪枝优化：剩余元素不足以选够 k 个数
    if (i < d) {
        return;
    }
    // 选
    path.add(i);
    dfs(i - 1, k);
    path.removeLast();
    // 不选
    dfs(i - 1, k);
}

216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9
每个数字「最多使用一次」
返回「所有可能的有效组合的列表」。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

避免组合重复只需要从「选或不选」的角度思考就很容易解决。

定义 dfs(i,d,t) 表示从数字 1 \dots i 中选择 d 个数和为 t 的所有情况，考虑当前数字 i 选或不选：

选，递归到 dfs(i-1, d-1, t-i)
不选，递归到 dfs(i-1,d,t)

由于我们按照顺序对数字进行「选或不选」，数字 1~9 本身不存在重复，因此不会出现重复组合。

本题需要进行剪枝优化才能过：

t < 0 时，无论怎么选都不可以满足条件，结束递归
当选择所有剩余最大的元素都不能满足 t 时，结束递归
剩余数字不够选时，结束递归

递归边界：数字选够了 d=0，且 t=0。

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

public List<List<Integer>> combinationSum3(int k, int n) {
    dfs(9, k, n);
    return ans;
}

public void dfs(int i, int k, int t) {
    int d = k - path.size(); // 还需要选 d 个数
    // 剪枝优化
    if (t < 0 || t > (i * 2 - d + 1) * d / 2) {
        return;
    }
    if (d == 0) {
        ans.add(new ArrayList<>(path));
        return;
    }
    // 剪枝：剩余元素不够选
    if (i < d){
        return;
    }
    // 选
    path.add(i);
    dfs(i - 1, k, t - i);
    path.removeLast();
    // 不选
    dfs(i - 1, k, t);
}

22. 括号生成

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

这道题可以转换为从 2n 个位置中选 n 个位置放左括号，因此是组合型回溯。

int n;
char[] path;
List<String> ans = new ArrayList<>();

public List<String> generateParenthesis(int n) {
    this.n = n;
    path = new char[n * 2];
    dfs(0, 0);
    return ans;
}

// i：目前要填括号的位置
// leftCnt：左括号的个数
public void dfs(int i, int leftCnt){
    // 括号构造完毕
    if (i == path.length){
        ans.add(new String(path));
        return;
    }
    // 左括号的个数未达上限
    if (leftCnt < n){
        path[i] = '(';
        dfs(i + 1, leftCnt + 1);
    }
    // 右括号 < 左括号 时才能填右括号
    if (i - leftCnt < leftCnt){
        path[i] = ')';
        dfs(i + 1, leftCnt);
    }
}

四、排列型回溯

46. 全排列

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

排列与组合不同的是，不同的顺序也是不同的排列。所有排列的长度是相同的，我们需要考虑每个位置上该选择什么数，已经选择的数不能再选。

使用数组 path 记录路径上的数字（已选的数），布尔数组 used 记录已经选择的数字。
枚举第 i 个位置可以选择的数字，选择可以选择的数字；
向后枚举第 i + 1 个位置可以选择的数字，当 i = n 时结束递归，保存答案

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

public List<List<Integer>> permute(int[] nums) {
    dfs(0, nums, new boolean[nums.length]);
    return ans;
}

public void dfs(int i, int[] nums, boolean[] used) {
    if (i == nums.length) {
        ans.add(new ArrayList<>(path));
        return;
    }
    // 枚举第 i 个位置可以选择的数字
    for (int j = 0; j < nums.length; j++) {
        if (used[j]) {
            continue;
        }
        // 选择 nums[j]
        path.add(nums[j]);
        used[j] = true;
        // 向后枚举第 i + 1 个位置
        dfs(i + 1, nums, used);
        // 恢复现场
        path.removeLast();
        used[j] = false;
    }
}