LeetCode 77. 组合
给定两个整数 n 和 k , 返回 [1,n] 中所有可能的 k 个数的组合,无顺序。
-
考到了回溯算法,这和之前学的多源bfs有一点点相似,具体的区别我还是很模糊。
-
再有 java 可以用List接口定义一个 ArrayList,符合java的动态绑定机制。
class Solution { //公用的变量,可以放在类的属性里 List<List<Integer>>ans = new ArrayList<List<Integer>>(); LinkedList<Integer> path = new LinkedList<Integer>(); //主函数 public List<List<Integer>> 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(); } } }