算法日记day 24（回溯之组合问题）

一、组合总和3

题目：

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字1到9
每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

示例 3:

输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。

思路：

这里有两个限制条件，第一个只能找k个数，第二个这k个数相加必须等于n，因此我们可以在遍历一个数时同时存入一个数组中，同时计算他的和，如果等于n的值则返回所有数，这里需注意，有些情况并不需要进行判断，例如n=3的情况，这时我们遍历4之后的数字就将没有任何意义了，所以当遍历的值本身就大于n时就不需要再遍历了

代码：

class Solution {// 结果集，存储所有符合条件的组合List<List<Integer>> result = new ArrayList<>();// 当前路径，用于存储正在构建的组合LinkedList<Integer> path = new LinkedList<>();// 主方法，返回所有的组合public List<List<Integer>> combinationSum3(int k, int n) {// 调用递归方法开始求解combination(k, n, 1, 0);// 返回最终的结果集return result;}// 递归方法，用于生成组合public void combination(int k, int n, int startIndex, int sum) {// 剪枝，如果当前的和超过了目标值n，直接返回if (sum > n)return;// 如果当前路径的长度等于k，并且当前和等于n，找到一个有效组合，加入结果集if (path.size() == k) {if (sum == n)result.add(new ArrayList<>(path));return;}// 从startIndex开始尝试每个数字，确保不重复选择已经选过的数字for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {path.add(i); // 将当前数字i加入路径中sum += i; // 更新当前的和// 递归调用，继续向下选择下一个数字，注意startIndex设置为i + 1，避免重复选择当前数字icombination(k, n, i + 1, sum);path.removeLast(); // 回溯，移除路径中的最后一个数字，尝试下一个可能的数字sum -= i; // 回溯，更新当前的和，恢复到之前的状态}}
}

变量说明：
- result 是用来存储所有符合条件的组合的列表。
- path 是一个 LinkedList<Integer>，用来存储当前正在构建的组合。
方法 combinationSum3：
- 在该方法中，调用 combination(k, n, 1, 0)，从数字 1 开始尝试生成符合要求的组合。
方法 combination：
- 它接受四个参数：
  - k：还需要选择的数字个数。
  - n：目标和。
  - startIndex：当前可选择的起始数字。
  - sum：当前已选数字的和。
- 方法的第一部分是两个基本的终止条件：
  - if (sum > n)：如果当前已选数字的和超过了目标和 n，则直接返回，因为当前路径不符合条件。
  - if (path.size() == k)：如果 path 中的数字个数达到了 k，则检查当前和 sum 是否等于 n。如果是，则将 path 的内容加入 result 中，表示找到了一个符合要求的组合。
- 如果上述两个终止条件都不满足，说明需要继续选择数字来构建组合。这时候会进入 for 循环：
  - for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++)：这个循环从 startIndex 开始，到 9 - (k - path.size()) + 1 结束。这个范围是为了确保即使选择了当前可能的最大值，也不会超过剩余需要选择的数目。
- 在循环体内部：
  - path.add(i)：将当前选择的数字 i 添加到 path 中。
  - sum += i：更新当前的和。
  - combination(k, n, i + 1, sum)：递归调用 combination 方法，继续选择下一个数字。递归调用的参数中 startIndex 设置为 i + 1，确保不重复使用相同的数字。
  - path.removeLast()：回溯，将刚刚添加的数字 i 移除，准备尝试下一个数字。
  - sum -= i：回溯，将之前添加的数字 i 从当前的和中减去，恢复到之前的状态。

二、电话号码的字母组合

题目：

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

思路：

首先需要定义一个字符串对应电话中每一个数字所对应的字母，用一个String类型的字符串保存所需的第几个数字所对应的字母，遍历当前字母，然后递归处理下一个数字，直到所有情况遍历完毕后，返回到一个结果数组中。

代码：

List<String> list = new ArrayList<>(); // 用于存储所有生成的字母组合的列表public List<String> letterCombinations(String digits) {if (digits == null || digits.length() == 0) {return list; // 如果输入为空，则直接返回空列表}// 数字键对应的字母字符串数组String[] numString = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };// 调用回溯方法开始生成所有可能的组合backTracking(digits, numString, 0);return list; // 返回生成的所有字母组合列表
}StringBuilder sb = new StringBuilder(); // 用于构建当前正在生成的字母组合的字符串public void backTracking(String digits, String[] numString, int num) {// 如果当前处理的数字索引等于输入数字串的长度，说明已经生成了一个有效组合if (num == digits.length()) {list.add(sb.toString()); // 将当前的StringBuilder内容转换为String并加入到结果列表中return; // 返回结束当前递归分支}// 获取当前数字对应的字母字符串String str = numString[digits.charAt(num) - '0'];// 遍历当前数字对应的所有可能字母for (int i = 0; i < str.length(); i++) {sb.append(str.charAt(i)); // 将当前字母加入StringBuilder中backTracking(digits, numString, num + 1); // 递归处理下一个数字sb.deleteCharAt(sb.length() - 1); // 回溯，删除最后一个字符，准备处理下一个可能的字母}
}

list 是用来存储所有生成的字母组合的列表。
sb 是一个用于构建当前正在生成的字母组合的字符串。
如果 digits 为 null 或者空字符串，则直接返回空列表 list。
numString 是一个数组，用于存储每个数字键对应的可能字母的字符串。例如，数字 2 对应 "abc"，数字 3 对应 "def"，依此类推。
调用 backTracking 方法开始生成所有可能的组合。
num 参数表示当前处理的 digits 的索引。
如果 num 等于 digits.length()，说明已经构建完成一个有效的组合，将当前 sb 中的内容转换为字符串并加入 list 中。
获取当前数字对应的字母字符串 str，例如，如果 digits.charAt(num) 是 '2'，则 str 是 "abc"。
使用 for 循环遍历 str 中的每个字符，将其加入 sb 中，然后递归调用 backTracking 处理下一个数字。
在递归调用之后，需要回溯，即删除 sb 的最后一个字符，以便进行下一次循环。

三、组合总和

题目：

给你一个 无重复元素 的整数数组 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
输出: []

与组合总和3的区别是，该题中有可以重复组合的元素

代码：

List<List<Integer>> result = new ArrayList<>(); // 存储所有满足条件的组合的列表
LinkedList<Integer> path = new LinkedList<>(); // 当前正在生成的一个组合public List<List<Integer>> combinationSum(int[] candidates, int target) {Arrays.sort(candidates); // 对candidates数组进行排序，方便后续处理backTracking(result, path, candidates, target, 0, 0); // 调用回溯算法开始生成组合return result; // 返回所有满足条件的组合列表
}public void backTracking(List<List<Integer>> result, LinkedList<Integer> path, int[] candidates, int target,int sum, int idx) {if (sum == target) { // 如果当前组合的和等于目标值result.add(new ArrayList<>(path)); // 将当前组合加入结果列表中return; // 结束当前分支的递归}for (int i = idx; i < candidates.length; i++) { // 遍历candidates数组，从当前索引idx开始if (sum + candidates[i] > target)break; // 如果加上当前元素后超过目标值，则跳出循环（因为数组已经排序）path.add(candidates[i]); // 将当前元素加入当前组合中backTracking(result, path, candidates, target, sum + candidates[i], i); // 递归调用，继续向下生成组合path.removeLast(); // 回溯，移除最后一个元素，准备生成下一个可能的组合//path.remove(path.size() - 1);}
}

result 是存储所有满足条件的组合的列表。
path 是一个链表，用于存储当前正在生成的一个组合。
combinationSum 方法首先对 candidates 数组进行排序，然后调用 backTracking 方法开始生成组合。
backTracking 方法是一个递归函数，用于生成所有可能的组合，其参数包括 result（结果列表）、path（当前正在生成的组合）、candidates（候选数组）、target（目标值）、sum（当前组合的和）、idx（当前处理的候选元素索引）。
在 backTracking 方法中，如果当前组合的和等于目标值 target，则将当前 path 中的元素加入 result 中。
然后使用循环遍历 candidates 数组，从索引 idx 开始，依次尝试加入数组中的元素到 path 中，如果加入后组合的和超过了 target，则跳出循环，因为数组已经排序。
如果未超过 target，则递归调用 backTracking 方法，继续生成下一个可能的组合。
每次递归完成后，执行 path.removeLast() 进行回溯，移除最后一个元素，以便尝试下一个可能的组合。

四、组合总和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]
]

示例 2:

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

思路：

与前两种组合总和问题不同，本题中传入的数据有重复元素，在遍历过程中可能会出现重复的情况，因此该题的重点在于如何去重。

代码：

List<List<Integer>> result = new ArrayList<>(); // 存储所有满足条件的唯一组合的列表
LinkedList<Integer> path = new LinkedList<>(); // 当前正在生成的一个组合
boolean[] used; // 记录每个元素是否被使用过的标记数组public List<List<Integer>> combinationSum2(int[] candidates, int target) {used = new boolean[candidates.length]; // 初始化used数组Arrays.fill(used, false);  //默认都为falseArrays.sort(candidates); // 对candidates数组进行排序，方便后续处理backTracking(candidates, target, 0, 0); // 调用回溯算法开始生成组合return result; // 返回所有满足条件的唯一组合列表
}public void backTracking(int[] candidates, int target, int sum, int startIndex) {if (sum == target) { // 如果当前组合的和等于目标值result.add(new ArrayList<>(path)); // 将当前组合加入结果列表中return; // 结束当前分支的递归}for (int i = startIndex; i < candidates.length; i++) { // 遍历candidates数组，从当前索引startIndex开始if (sum + candidates[i] > target)break; // 如果加上当前元素后超过目标值，则跳出循环（因为数组已经排序）if (i > startIndex && candidates[i] == candidates[i - 1] && !used[i - 1]) {continue; // 跳过重复的元素，确保每个元素只使用一次}used[i] = true; // 标记当前元素已被使用sum += candidates[i]; // 更新当前组合的和path.add(candidates[i]); // 将当前元素加入当前组合中backTracking(candidates, target, sum, i + 1); // 递归调用，继续向下生成组合used[i] = false; // 回溯，标记当前元素未使用sum -= candidates[i]; // 回溯，恢复当前组合的和path.removeLast(); // 回溯，移除最后一个元素，准备生成下一个可能的组合}
}

result 是存储所有满足条件的唯一组合的列表。
path 是一个链表，用于存储当前正在生成的一个组合。
used 是一个布尔数组，用于标记 candidates 数组中的元素是否被使用过。
combinationSum2 方法首先初始化 used 数组，并对 candidates 数组进行排序，然后调用 backTracking 方法开始生成组合。
backTracking 方法是一个递归函数，用于生成所有可能的组合，其参数包括 candidates（候选数组）、target（目标值）、sum（当前组合的和）、startIndex（当前处理的候选元素索引）。
在 backTracking 方法中，如果当前组合的和等于目标值 target，则将当前 path 中的元素加入 result 中。
然后使用循环遍历 candidates 数组，从索引 startIndex 开始，依次尝试加入数组中的元素到 path 中。
在循环内部，通过判断 used 数组和当前元素是否与上一个相同的方式，确保每个元素只被使用一次，避免生成重复的组合。
如果未超过 target，则递归调用 backTracking 方法，继续生成下一个可能的组合。
每次递归完成后，执行相应的回溯操作，包括标记当前元素未使用、恢复当前组合的和以及移除最后一个元素，以便尝试下一个可能的组合。

其中的去重代码为：

if (i > startIndex && candidates[i] == candidates[i - 1] && !used[i - 1]) {continue; // 跳过重复的元素，确保每个元素只使用一次
}

这里的具体解释为：

i > startIndex: 这个条件确保我们在处理候选数组时，只考虑从当前位置 startIndex 开始的元素。这是因为数组是经过排序的，如果一个元素与之前的元素相同，我们只需要考虑第一个出现的元素及其后续出现的。
candidates[i] == candidates[i - 1]: 这个条件检查当前元素 candidates[i] 是否与前一个元素 candidates[i - 1] 相同。这是为了避免重复的组合。在排序后的数组中，如果当前元素与前一个元素相同，并且前一个元素 used[i - 1] 已经被使用过（即为 true），说明我们已经考虑过将前一个元素加入组合了，所以当前元素不应该再被考虑。
!used[i - 1]: 这个条件确保前一个相同的元素 candidates[i - 1] 没有被使用过。如果前一个相同元素已经被使用过，即 used[i - 1] 为 true，说明我们已经在之前的组合中考虑过这个元素了，因此不应该再考虑当前元素 candidates[i]，以避免重复。