77. 组合

求组合，注意终止条件。

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

216. 组合总和 III

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

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

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

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

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"};
  11.         // 迭代处理
  12.         backTracking(digits,numString,0);
  13.         return list;
  14.     }
  16.     StringBuilder temp = new StringBuilder();
  18.     public void backTracking(String digits,String[] numString,int num){
  19.         if(num ==digits.length()){
  20.             list.add(temp.toString());
  21.             return;
  22.         }
  24.         String str = numString[digits.charAt(num)-'0'];
  25.         for(int i = 0;i<str.length();i++){
  26.             temp.append(str.charAt(i));
  27.             backTracking(digits,numString,num+1);
  28.             temp.deleteCharAt(temp.length()-1);
  29.         }
  30.     }
  31. }