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