Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
For example,
If n = 4 and k = 2, a solution is:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
題意：給出數(shù)字n和k伊诵，返回從1到n中k個(gè)數(shù)字的組合厕隧。
思路：深度優(yōu)先搜索，從1開始選凳枝，逐個(gè)選下一個(gè)驴剔，選到的數(shù)組集合滿足k個(gè)以后將這個(gè)集合加到結(jié)果集中省古，然后把這個(gè)結(jié)果集中最后一個(gè)數(shù)字刪掉，回溯的加下一個(gè)數(shù)字丧失。比如n是4豺妓，k是3的情況，選出123后布讹；刪掉3琳拭，加入3的下一個(gè)數(shù)字4，得到124描验。
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<>();
if (n <= 0 || k > n) {
return res;
}
dfs(n, k, 1, new ArrayList<>(), res);
return res;
}
private void dfs(int n, int k, int start, List<Integer> subres, List<List<Integer>> res) {
if (subres.size() == k) {
res.add(new ArrayList<>(subres));
return;
}
// for (int i = start; i <= n - k + 1; i++) {
for (int i = start; i <= n; i++) {
// subres.add(start);
// dfs(n, k, start + 1, subres, res);
subres.add(i);
dfs(n, k, i + 1, subres, res);
subres.remove(subres.size() - 1);
}
}
bug：1臀栈、循環(huán)內(nèi)處理subres.add和dfs時(shí)傳入的是start參數(shù)；2挠乳、想到如果4個(gè)數(shù)選3個(gè)數(shù)的情況，如果第一個(gè)數(shù)字選到了3姑躲，那么是沒有符合條件的組合的睡扬，所以循環(huán)終止條件寫成了i<=n-k+1，但是沒有考慮到選后面幾個(gè)數(shù)字也會(huì)調(diào)用到這里黍析。
