time: O(2^n) or O(2^n*n) , the subset's count is 2^n
space: O(2^n) or O(2^n*n)
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> result = new ArrayList<>();
dfs(n, k, result, new ArrayList<>(), 1);
return result;
}
private void dfs(int n, int k, List<List<Integer>> result, List<Integer> list, int start) {
if (list.size() == k) {
result.add(new ArrayList<>(list));
}
for (int i = start; i <= n; i++) {
list.add(i);
dfs(n, k, result, list, i+1);
list.remove(list.size()-1);
}
}
}
why i <= n - k + 1
For anyone stumped by why this change is necessary, it's because you should not continue exploring (recursing) when you know that there won't be enough numbers left until n to fill the needed k slots. If n = 10, k = 5, and you're in the outermost level of recursion, you choose only i = 1...6 , because if you pick i=7 and go into backTracking() you only have 8,9,10 to pick from, so at most you will get [7,8,9,10]... but we need 5 elements!
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> result = new ArrayList<>();
backtrack(result, new ArrayList<>(), 1, n, k);
return result;
}
private void backtrack(List<List<Integer>> result, List<Integer> tempList, int start, int n, int k) {
if (k == 0) {
result.add(new ArrayList<>(tempList));
} else {
for (int i = start; i <= n-k+1; i++) {
tempList.add(i);
backtrack(result, tempList, i+1, n, k - 1);
tempList.remove(tempList.size() - 1);
}
}
}
}
time: O( k*c(n, k))
space: O( k*c(n, k))
use <= n
class Solution {
public List<List<Integer>> combine(int n, int k) {
// use backtracking
// 1, 2, 3, 4 k=2
// 2 3 4 3. 4 4
List<List<Integer>> res = new ArrayList<>();
helper(res, new ArrayList<>(), n, k, 1);
return res;
}
private void helper(List<List<Integer>> res, List<Integer> list, int n, int k, int start) {
if (k == 0) {
res.add(new ArrayList<>(list));
return;
}
for (int i = start; i <= n; i++) {
list.add(i);
helper(res, list, n, k-1, i + 1);
list.remove(list.size()-1);
}
}
}
