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:
代码语言：javascript复制[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]递归，选择数字k次，每次选择的数字都比前一个大。
代码语言：javascript复制 int target;// 次数
Integer[] stack;// 存储每次排列
Integer[] nums;// 存储1~n
List<List<Integer>> rt;// 存储结果
public void search(int p) {
// 若长度为k，则stack是其中一个结果，保存结果
if (p == target) {
rt.add(new ArrayList<Integer>(Arrays.asList(stack)));
return;
}
// 对于nums(1~n)中的每个元素
for (Integer n : nums) {
// 找到nums中第一个比stack最后元素大的元素
if (p > 0 && n <= stack[p - 1]) {
continue;
}
// 找到下一个元素，递归
stack[p] = n;
search(p 1);
}
}
public List<List<Integer>> combine(int n, int k) {
target = k;
nums = new Integer[n];
stack = new Integer[k];
for (int i = 0; i < nums.length; i ) {
nums[i] = i 1;
}
rt = new ArrayList<List<Integer>>();
search(0);
return rt;
}
