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]]
Constraints:
- 1 <= n <= 20
- 1 <= k <= n
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<>();
backtrack(res, new ArrayList(), n, k,1);
return res;
}
private void backtrack(List<List<Integer>> res, List<Integer> tempList, int n, int k,int start){
if(tempList.size()==k){
res.add(new ArrayList(tempList));
return;
}
for(int i=start; i<=n; i++){
tempList.add(i);
backtrack(res,tempList,n,k,i+1);
tempList.remove(tempList.size()-1);
}
}
}模板分析
List<List<T>> result = new ArrayList<T>();
public void backtrack(List<List<T>> result, List<T>subList, int index){
// 满足条件
if(subList.size()==index){
result.add(subList);
return;
}
for(...){
// 做选择
subList.add(i);
backtrack(result, subList, index+1);
// 撤销选择
subList.remove(subList.size()-1);
}
}