題目
給定兩個整數 n 和 k,傳回 1 … n 中所有可能的 k 個數的組合。
示例:
輸入: n = 4, k = 2
輸出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
解題
- 遞歸 + 回溯
class Solution {
List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
if (n < 1 || n < k) {
return result;
}
combine(n, k, 1, new ArrayList<>());
return result;
}
private void combine(int n, int k, int index, List<Integer> temp) {
if (k == 0) {
result.add(new ArrayList<>(temp));
return;
}
for (int i = index; i <= n - k + 1; i++) {
temp.add(i);
combine(n, k - 1, i + 1, temp);
temp.remove(temp.size() - 1);
}
}
}
類似題目
39. 組合總和
40. 組合總和 II
216. 組合總和 III