Description
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],
]
Solution
DFS
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> combinations = new ArrayList<>();
if (n < 1 || k < 1 || k > n) return combinations;
List<Integer> combination = new ArrayList<>();
combineRecur(1, n, k, combination, combinations);
return combinations;
}
public void combineRecur(int begin, int end, int count
, List<Integer> combination
, List<List<Integer>> combinations) {
if (count == 0) {
combinations.add(new ArrayList<>(combination));
return;
}
for (int i = begin; i <= Math.min(end, end + 1 - count); ++i) {
combination.add(i);
combineRecur(i + 1, end, count - 1, combination, combinations);
combination.remove(combination.size() - 1);
}
}
}
