给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
public List<List<Integer>> combine(int n, int k) {
ArrayList<List<Integer>> res = new ArrayList<>();
if (n <= 0 || k > n) {
return res;
}
helper(1, n, k, new ArrayList<Integer>(), res);
return res;
}
private void helper(int currentVal, int limit, int count, ArrayList<Integer> path, ArrayList<List<Integer>> res) {
if (count == 0) {
res.add(new ArrayList<Integer>(path));
return;
}
if (currentVal > limit) {
return;
}
for (int i = currentVal; i <= limit; i++) {
path.add(i);
helper(i + 1, limit, count - 1, path, res);
path.remove(path.size() - 1);
}
}
时间复杂度为题解个数 n!/ (n - k)! / k!
