77. Combinations --【M】Backtracking
https://leetcode.com/problems/combinations/
51 ms 28.32%
public class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> result = new ArrayList<>();
if (k == 0 || n < k)
return result;
dfs(result, new ArrayList<>(), n, k, 1);
return result;
}
public void dfs(List<List<Integer>> result, List<Integer> list, int n, int k, int start) {
if (list.size() == k) {
result.add(new ArrayList<Integer>(list));
return;
}
for (int i = start; i <= n; i++) {
if (list.contains(i))
continue;
list.add(i);
dfs(result, list, n, k, i+1);
list.remove(list.size() - 1);
}
}
}
**总结：
本质：Combination 类问题是典型的搜索问题，除了 DFS + backtracking 之外，combination 里最重要的就是“去重”，注意两点：已知数组本身有没有重复，如果没有就简单start + 1法，此题没有。怎么让自己的搜索树不回头地往前走。传参一个start，递归+1