LeetCode 77. 组合

给定两个整数 n 和 k ， 返回 [1,n] 中所有可能的 k 个数的组合，无顺序。

• 考到了回溯算法，这和之前学的多源bfs有一点点相似，具体的区别我还是很模糊。

• 再有 java 可以用List接口定义一个 ArrayList，符合java的动态绑定机制。

  class Solution {
  //公用的变量，可以放在类的属性里
          List>ans = new ArrayList>();
          LinkedList path = new LinkedList();
  //主函数        
      public List> combine(int n, int k) {
      backtracking(1,n,k);
      return ans;    
      }
  //递龟函数，
      void backtracking(int i , int n , int k){
          
          if(path.size()==k){
              ans.add(new LinkedList(path));
              return;
          }
  //这里为了剪枝 k-path.size 表示还需要多少数字， 整体就表示至少j的下标为多少才能保证
  //有k个数可以组成一个数组
          for(int j = i; j<=n-(k-path.size())+1  ;j++){
                  path.add(j);
  //想象一下程序一运行到这里，就开了一个新栈，在新栈里从头运行（变了个参数），，，直到最后一个
  //程序path.size == k，这时候最里边，也就是最后开的程序栈结束，
  //对应着倒数第二个栈的backtracking执行完了，走到了path.remove
  //然后继续倒数第二个的for。。。
                  backtracking(j+1, n , k);
                  path.removeLast();
          }
      }
  }