LeetCode 77.组合 回溯

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();
            }
        }
    }
    

LeetCode 77.组合  回溯

上一篇:python – PyQt QTreeWidget.clear()导致崩溃


下一篇:You have 77 PMD violations maven error