回溯算法。
组合：
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
思路：如果用暴力解法，k=2，两层for循环就可以搞定，那么k=50要多少层for循环，是不合理的。
所以可以用递归的思路来完成，k的次数为递归的次数，在每次递归里进行循环。
回溯的三个步骤：
- 递归函数的返回值以及参数
- 回溯函数的终止条件
- 回溯函数的单层搜索过程
1.参数和返回值。 参数为n,k,startIndex(每次遍历的起始位置，防止重复) 由于是不可取重复次数，所以每个数只能取一次，第一次取1，下次取2,3,4
2.回溯的终止条件。 集合大小等于k
3.单层搜索过程：
for (int i = startIndex; i <= n; i++) { // 控制树的横向遍历
path.push_back(i); // 处理节点
backtracking(n, k, i + 1); // 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始
path.pop_back(); // 回溯，撤销处理的节点
}
最终代码：
import java.util.ArrayList;
import java.util.List;
public class Combinations {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> results = new ArrayList<>();
backtrack(new ArrayList<>(), 1, n, k, results);
return results;
}
private void backtrack(List<Integer> combination, int start, int n, int k, List<List<Integer>> results) {
if (combination.size() == k) {
results.add(new ArrayList<>(combination));
return;
}
for (int i = start; i <= n; i++) {
combination.add(i);
backtrack(combination, i + 1, n, k, results);
combination.remove(combination.size() - 1);
}
}
public static void main(String[] args) {
int n = 4;
int k = 2;
Combinations combinations = new Combinations();
List<List<Integer>> result = combinations.combine(n, k);
for (List<Integer> combination : result) {
System.out.println(combination);
}
}
}