Java日记2018-08-02

Combinations-

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,

If n = 4 and k = 2, a solution is:

[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

给出一个n和k,要求求出由n中k个不同的数组成是序列,使用回溯的方法求解，对于每次判断的边界条件为：后面的数要大于前面的数,由于这里1到n肯定是递增的，所以继续进行下一层运算的条件可以为 当前位置后面的数

public static ArrayList<ArrayList<Integer>> combine(int n,int k){
        ArrayList<ArrayList<Integer>> res = new  ArrayList<>();
        ArrayList<Integer> lst = new ArrayList<>();
        dfs(n,k,1,1,res,lst);
        return res;
    }
    public static void dfs(int n,int k,int t,int start,ArrayList<ArrayList<Integer>> res,ArrayList<Integer> lst){
        //t记录当前list的数量，如果t大于需要的数组的大小k时，可以计入结果
        if(t>k){
            //System.out.println(lst.get(0));
            res.add(new ArrayList<>(lst));
        } else {
            for(int i=start;i<=n;i++){
                lst.add(i);
                //下一个目的数组应该是当前的数的后一位，即i+1，并且将当前数组大小同时加1即t+1,用于判断是否该记录结果了
                dfs(n,k,t+1,i+1,res,lst);
                lst.remove(lst.size()-1);
            }
            
        }
        
    }