阅读量:0
代码随想录算法训练营第22天| 77. 组合216.组合总和III17.电话号码的字母组合
Leetcode 77. 组合
题目链接：https://leetcode.cn/problems/combinations/description/
题目描述：
给定两个整数 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 <= 201 <= k <= n
思路：
1、回溯
2、剪枝
图示：
代码1：回溯
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; } // 回溯 public void backTracking(int n ,int k , int startIndex){ // 终止条件 if(path.size() == k){ // 存放结果 res.add(new ArrayList<>(path)); return; } // 单层递归逻辑 for(int i = startIndex ; i <= n ; i++){ path.add(i); backTracking( n , k , i + 1); path.removeLast(); } // removeLast()方法用于返回最后一个元素，但要从此双端队列移除该元素。 } } 代码2：剪枝
class Solution { // 声明单条路径 LinkedList<Integer> path = new LinkedList<>(); // 声明结果 List<List<Integer>> res = new ArrayList<>(); public List<List<Integer>> combine(int n, int k) { // 剪枝优化 backTracking(n , k , 1); return res; } public void backTracking(int n ,int k , int startIndex){ // 终止条件 if(path.size() == k){ // 收集好了，添加至res res.add(new ArrayList<>(path)); return; } // 单层的回溯逻辑 for(int i = startIndex ; i <= (n - (k - path.size()) + 1) ; i++){ // n - (k - path.size()) + 1 为至多要从该位置遍历 path.add(i); backTracking(n ,k , i + 1); path.removeLast(); } } } 总结：
Leetcode 216.组合总和III
题目链接：https://leetcode.cn/problems/combination-sum-iii/
题目描述：找出所有相加之和为 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，没有有效的组合。 提示:
2 <= k <= 91 <= n <= 60
思路：
1、回溯
2、剪枝
图示：
代码1：回溯
class Solution { // 单个路径 LinkedList<Integer> path = new LinkedList<>(); // 结果 List<List<Integer>> res = new ArrayList<>(); public List<List<Integer>> combinationSum3(int k, int n) { backTracking( k , n , 0 , 1); return res; } // 回溯算法 public void backTracking(int k , int targetSum , int sum , int startIndex){ // 终止条件 if(path.size() == k){ if(targetSum == sum){ res.add(new LinkedList<>(path)); return; } } // 单层递归逻辑 for(int i = startIndex ; i <= 9 ; i++){ path.add(i); sum += i; backTracking( k , targetSum , sum , i + 1); // startIndex防止组合中出现重复结果 sum = sum - i; path.removeLast(); } } } 代码2：剪枝
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 , 0 , 1); return res; } public void backTracking(int k , int targetSum , int sum , int startIndex){ // 终止条件 if(targetSum < sum){ return; } if(path.size() == k){ if(targetSum == sum){ res.add(new LinkedList<>(path)); return; } } // 单层 for(int i = startIndex ; i <= (9 - (k - path.size())) + 1 ; i++){ path.add(i); sum += i; backTracking( k , targetSum ,sum , i + 1); path.removeLast(); sum -= i; } } } 总结：
注意：此题每个数字 最多使用一次 ，该列表不能包含相同的组合两次
所以startIndex后续加1
Leetcode 17.电话号码的字母组合
题目链接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/
题目描述：
输入：digits = "2" 输出：["a","b","c"] 提示：
0 <= digits.length <= 4digits[i]是范围['2', '9']的一个数字。
思路：
1、回溯
图示：
代码1：回溯
class Solution { // 声明结果 List<String> res = new ArrayList<>(); public List<String> letterCombinations(String digits) { // 排空 if(digits == null || digits.length() == 0){ return res; } // 定义数字对应的字符串 //初始对应所有的数字，为了直接对应2-9，新增了两个无效的字符串"" String[] strNum = {"", //0 "", //1 "abc", //2 "def", //3 "ghi", //4 "jkl", //5 "mno", //6 "pqrs", "tuv", "wxyz"}; backTracking(digits , strNum , 0); return res; } //每次迭代获取一个字符串， // 所以会涉及大量的字符串拼接， // 所以这里选择更为高效的 StringBuilder StringBuilder stringB = new StringBuilder(); // num 用来记录当前遍历第几个数字 public void backTracking(String digits , String[] strNum , int num){ // 终止条件 if(num == digits.length()){ res.add(stringB.toString()); return; } //str 代表 num 对应的字符串 String str = strNum[digits.charAt(num) - '0']; // charAt()是一种从指定索引返回字符的方法，字符串中的字符从左到右索引。 // 单层递归逻辑 for( int i = 0 ; i < str.length(); i++){ stringB.append(str.charAt(i)); backTracking(digits , strNum , num + 1); //剔除末尾的继续尝试 stringB.deleteCharAt(stringB.length() - 1); } } } 总结：
本题难点在于
//str 代表 num 对应的字符串
String str = strNum[digits.charAt(num) - ‘0’];
（仅代表个人观点）
