# 77. Combinations
Question link is here.
Given two integers n
and k
, return all possible combinations of k
numbers out of the range [1, n]
.
You may return the answer in any order.
Example 1:
Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
Example 2:
Input: n = 1, k = 1
Output: [[1]]
# Solution
Easy, use backtrack will be enough.
class Solution {
int k;
int n;
List<List<Integer>> res = new LinkedList<List<Integer>>();
public void helper(int start, LinkedList<Integer> path) {
if(path.size() == k) {
res.add(new LinkedList(path));
}
for(int i = start; i <= n; i++) {
path.add(i);
helper(i+1, path);
path.removeLast();
}
}
public List<List<Integer>> combine(int n, int k) {
this.k = k;
this.n = n;
helper(1, new LinkedList<Integer>());
return res;
}
}