代码随想录 算法训练 Day22：回溯算法part01

题目一

给定两个整数 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]]

提示：

• 1 <= n <= 20
• 1 <= k <= n

class Solution {List<Integer> path = new ArrayList<>();List<List<Integer>> result = new ArrayList<>();public List<List<Integer>> combine(int n,int k){backtracking(n,k,1);return result;}public void backtracking(int n,int k,int start){if(path.size() == k){result.add(new ArrayList<>(path));return;}for(int i = start;i <= n;i++){// 循环内剪枝（当前剩余元素不够）if((path.size() + n - i + 1) < k) break;path.add(i);backtracking(n,k,i + 1);path.remove(path.size() - 1);}}
}

题目二

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

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

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

class Solution {List<Integer> path = new ArrayList<>();List<List<Integer>> result = new ArrayList<>();int sum = 0;public List<List<Integer>> combinationSum3(int k, int n) {backtracking(k,n,1);return result;}public void backtracking(int k,int n,int start){if (sum > n) return;if(path.size() == k&&sum == n){result.add(new ArrayList<>(path));return;}for(int i = start ; i <= 9 ;i++){if((sum + i > n)||(path.size() + 10 - i < k)) break;sum = sum + i;path.add(i);backtracking(k,n,i + 1);path.remove(path.size() - 1);sum = sum - i;}}
}

题目三

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

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

示例 1：

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

示例 2：

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

示例 3：

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

class Solution {// 数字到字母的映射表private static final String[] LETTER_MAP = {"",     // 0"",     // 1"abc",  // 2"def",  // 3"ghi",  // 4"jkl",  // 5"mno",  // 6"pqrs", // 7"tuv",  // 8"wxyz"  // 9};public List<String> letterCombinations(String digits) {List<String> result = new ArrayList<>();if (digits == null || digits.isEmpty()) {return result;}backtrack(result, new StringBuilder(), digits, 0);return result;}// 回溯核心方法private void backtrack(List<String> result, StringBuilder current, String digits, int index) {// 终止条件：当前组合长度等于输入数字长度if (index == digits.length()) {result.add(current.toString());return;}// 获取当前数字对应的字母字符串char digit = digits.charAt(index);String letters = LETTER_MAP[digit - '0']; // 将字符转为数字索引// 遍历所有可能的字母for (int i = 0; i < letters.length(); i++) {// 添加当前字母current.append(letters.charAt(i));// 递归处理下一个数字backtrack(result, current, digits, index + 1);// 回溯：删除最后添加的字母current.deleteCharAt(current.length() - 1);}}
}