目录
77. 组合
216. 组合总和 III
17. 电话号码的字母组合
给定两个整数
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
状态:完成
思路:用一个全局变量result来装结果,然后用回溯得到结果,用一个start来标记起始的位置,避免重复的值出现,传递list参数记录路径,回溯的终止条件就是list.size()==k,把list放入result里面,这里还有一个剪枝的操作就是如果这一层的节点不够就不要向后遍历了,for循环的终止条件是n-(k-list.size())+1,这个表达式的意思就是这一层应该要取多少。
class Solution {List<List<Integer>> result =new ArrayList<>();public List<List<Integer>> combine(int n, int k) {ArrayList<Integer> nums=new ArrayList<>();for(int i=1;i<=n;i++){nums.add(i);}backtracing(new ArrayList<Integer>(),k,0,n);return result;}public void backtracing(ArrayList<Integer> list,int k,int start,int n){if(list.size()==k){ArrayList<Integer> list2=new ArrayList<>();list2.addAll(list);result.add(list2);return ;} for(int i=start;i<n-(k-list.size())+1;i++){list.add(i+1);backtracing(list,k,i+1,n);list.remove(list.size()-1);}}
}
216. 组合总和 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
状态:完成
思路:与上一题一样只不过回溯停止的条件是和等于目标值且集合中数量等于k。然后我们开始做剪枝,首先如果此时sum >target就可以返回了,因为没有负数只能是递增的。然后在for的时候也可以做剪枝,9-(k-road.size())但我没做。
class Solution {List<List<Integer>> list=new ArrayList<>();LinkedList<Integer> road=new LinkedList<>();public List<List<Integer>> combinationSum3(int k, int n) {backtracking(1,0,k,n);return list;}public void backtracking(int start,int sum,int k,int target){if(sum>target) return;if(sum==target&&road.size()==k){list.add(new ArrayList<Integer>(road));return;}for(int i=start;i<=9;i++){road.add(i);backtracking(i+1,sum+i,k,target);road.removeLast();}}
}
17. 电话号码的字母组合
给定一个仅包含数字
2-9
的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
示例 1:
输入:digits = "23" 输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]示例 2:
输入:digits = "" 输出:[]示例 3:
输入:digits = "2" 输出:["a","b","c"]提示:
0 <= digits.length <= 4
digits[i]
是范围['2', '9']
的一个数字。
状态:完成
思路:如题要返回所有的组合很自然的就想到了回溯,所以先把每个数字对应的字母装进数组中方便调用。然后回溯搜索所有结果,回溯的终止条件是digits.length()==0最后没有数字了就说明到最后了。这题使用StringBuilder,因为涉及很多字符串的操作。
class Solution {List<String> result=new ArrayList<>();StringBuilder target=new StringBuilder();public List<String> letterCombinations(String digits) {if(digits.isBlank()) return result;String[] arr=new String[8];arr[0]="abc";arr[1]="def";arr[2]="ghi";arr[3]="jkl";arr[4]="mno";arr[5]="pqrs";arr[6]="tuv";arr[7]="wxyz";backtracking(arr,digits);return result;}public void backtracking(String[] arr,String digits){if(digits.length()==0){result.add(target.toString());return;}int now=Integer.valueOf(digits.substring(0,1));for(int i=0;i<arr[now-2].length();i++){target.append(arr[now-2].charAt(i));backtracking(arr,digits.substring(1));target.deleteCharAt(target.length()-1);}}
}
感想:回溯这章之前刷过了,所以做起来还是很简单的,这章我就做快点,快点进入动规。