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個不同的數(shù)組成是序列,使用回溯的方法求解，對于每次判斷的邊界條件為：后面的數(shù)要大于前面的數(shù),由于這里1到n肯定是遞增的，所以繼續(xù)進(jìn)行下一層運(yùn)算的條件可以為 當(dāng)前位置后面的數(shù)

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記錄當(dāng)前l(fā)ist的數(shù)量，如果t大于需要的數(shù)組的大小k時，可以計入結(jié)果
        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);
                //下一個目的數(shù)組應(yīng)該是當(dāng)前的數(shù)的后一位，即i+1，并且將當(dāng)前數(shù)組大小同時加1即t+1,用于判斷是否該記錄結(jié)果了
                dfs(n,k,t+1,i+1,res,lst);
                lst.remove(lst.size()-1);
            }
            
        }
        
    }