给定两个整数 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、剪枝
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()方法用于返回最后一个元素,但要从此双端队列移除该元素。 } }
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(); } } }
n
的 k
个数的组合,且满足下列条件:返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。
示例 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、剪枝
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(); } } }
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
输入:digits = "2" 输出:["a","b","c"]
提示:
0 <= digits.length <= 4
digits[i]
是范围 ['2', '9']
的一个数字。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); } } }
String str = strNum[digits.charAt(num) - ‘0’];
(仅代表个人观点)