77. Combinations
Last updated
Last updated
/**
* Time complexity : O(k*kCn), where kCn = n!/((n-k)! * k!) is a number of
* combinations to build. append / pop (add / removeLast) operations are
* constant-time ones and the only consuming part here is to append the
* built combination of length k to the output.
* Space complexity : O(kCn) to keep all the combinations for an output.
*/
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> resultList = new ArrayList<>();
backtrack(resultList, new ArrayList(), 1, n, k);
return resultList;
}
private void backtrack(List<List<Integer>> resultList,
List<Integer> currList,
int start,
int end,
int k ) {
if(k == 0) {
resultList.add(new ArrayList(currList));
return;
}
for(int i = start; i <= end-k+1; i++) {
currList.add(i);
backtrack(resultList, currList, i+1, end, k-1);
currList.remove(currList.size()-1);
}
}
}