LeetCode - Combinations
Problem description
Given two integers n and k, return all possible combinations of k numbers out of 1 … n.
Example:
1
2
3
4
5
6
7
8
9
10
Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
Analysis
The general idea is to use backtrack.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<>();
backtrack(n, res, new ArrayList<>(), 1, k);
return res;
}
void backtrack(int n, List<List<Integer>> res, List<Integer> list, int start, int k){
if (list.size() == k){
res.add(new ArrayList(list));
}
for (int i = start; i < n+1; i++){
list.add(i);
backtrack(n, res, list, i+1, k);
list.remove(list.size() - 1);
}
}
}
There are something we can improve.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<>();
backtrack(n, res, new ArrayList<>(), 1, k);
return res;
}
void backtrack(int n, List<List<Integer>> res, List<Integer> list, int start, int k){
if (list.size() == k){
res.add(new ArrayList(list));
return;
}
int need = k - list.size();
for (int i = start; i < n+1 - need + 1; i++){
list.add(i);
backtrack(n, res, list, i+1, k);
list.remove(list.size() - 1);
}
}
}
What to improve
- make sure return in backtrack
- if we don’t have enough item to fit into the space, the part of the for loop should be dropped.