77. 组合

求组合,注意终止条件。

  1. class Solution {
  2. List<List<Integer> > res = new ArrayList<>();
  3. LinkedList<Integer> path = new LinkedList<>();
  4. public List<List<Integer>> combine(int n, int k) {
  5. combine(n,k,1);
  6. return res;
  7. }
  8. void combine(int n,int k,int index){
  9. if(path.size() == k) {
  10. // 这儿一定要返回的是new ArrayList<>(path)
  11. res.add(new ArrayList<>(path));
  12. return;
  13. }
  14. for(int i = index;i<=n-(k-path.size())+1;i++){
  15. path.add(i);
  16. combine(n,k,i+1);
  17. // 要用removeLast的前提是path需要定义为LinkedList
  18. path.removeLast();
  19. }
  20. }
  21. }

216. 组合总和 III

没有剪枝的时候,提交超时了。进行了剪枝才可以。

  1. class Solution {
  2. List<List<Integer>> res = new ArrayList<>();
  3. LinkedList<Integer> path = new LinkedList<>();
  4. public List<List<Integer>> combinationSum3(int k, int n) {
  5. backtracking(k,n,1,0);
  6. return res;
  7. }
  8. void backtracking(int k,int n,int startIndex,int sum){
  9. if(path.size()==k){
  10. if(sum==n){
  11. res.add(new ArrayList<>(path));
  12. }
  13. return;
  14. }
  15. for(int i = startIndex;i<=9-(k-path.size())+1;i++){
  16. path.add(i);
  17. sum+=i;
  18. backtracking(k,n,i+1,sum);
  19. path.removeLast();
  20. sum-=i;
  21. }
  22. }
  23. }

二刷的时候我没剪枝,然后也过了。

  1. class Solution {
  2. List<List<Integer>> res = new ArrayList<>();
  3. LinkedList<Integer> path = new LinkedList<>();
  4. public List<List<Integer>> combinationSum3(int k, int n) {
  5. combinationSum3(n,k,1);
  6. return res;
  7. }
  8. void combinationSum3(int n,int k,int index){
  9. // 终止条件 path.size() == k , n == 0
  10. if(path.size() == k){
  11. if(n == 0){
  12. res.add(new ArrayList<>(path));
  13. return;
  14. }
  15. }
  16. // 单层逻辑处理
  17. for(int i = index;i<=9;i++){
  18. path.add(i);
  19. combinationSum3(n-i,k,i+1);
  20. // 回溯处理
  21. path.removeLast();
  22. }
  23. }
  24. }

17. 电话号码的字母组合(抄)

  1. class Solution {
  2. // 设置全局链表来存储最后的结果
  3. List<String> list = new ArrayList<>();
  4. public List<String> letterCombinations(String digits) {
  5. if(digits==null||digits.length()==0){
  6. return list;
  7. }
  8. // 初始对应所有的数字,为了直接对应2-9,新增了两个无效的字符串
  9. String[] numString = {"","","abc","def", "ghi", "jkl", "mno","pqrs", "tuv", "wxyz"};
  10. // 迭代处理
  11. backTracking(digits,numString,0);
  12. return list;
  13. }
  14. StringBuilder temp = new StringBuilder();
  15. public void backTracking(String digits,String[] numString,int num){
  16. if(num ==digits.length()){
  17. list.add(temp.toString());
  18. return;
  19. }
  20. String str = numString[digits.charAt(num)-'0'];
  21. for(int i = 0;i<str.length();i++){
  22. temp.append(str.charAt(i));
  23. backTracking(digits,numString,num+1);
  24. temp.deleteCharAt(temp.length()-1);
  25. }
  26. }
  27. }