代码随想录算法训练营第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 <= 20
• 1 <= k <= n

思路：

1、回溯

2、剪枝

图示：

代码1：回溯

class Solution {     // 声明用来存放结果的数组     List> res = new ArrayList<>();     LinkedList path = new LinkedList<>();     public List> 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 path = new LinkedList<>();     // 声明结果     List> res = new ArrayList<>();     public List> 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 <= 9
• 1 <= n <= 60

思路：

1、回溯

2、剪枝

图示：

代码1：回溯

class Solution {     // 单个路径     LinkedList path = new LinkedList<>();     // 结果     List> res = new ArrayList<>();     public List> 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> res = new ArrayList<>();     LinkedList path = new LinkedList<>();     public List> 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 <= 4
• digits[i] 是范围 ['2', '9'] 的一个数字。

思路：

1、回溯

图示：

代码1：回溯

class Solution {     // 声明结果     List res = new ArrayList<>();     public List 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’];

（仅代表个人观点）