LeetCode077——组合
我的LeetCode代码仓:https://github.com/617076674/LeetCode
原题链接:https://leetcode-cn.com/problems/combinations/description/
题目描述:
知识点:递归、回溯
思路:回溯法穷举所有可能的组合
本题是回溯法的一个经典应用场景。注意两点:
(1)回溯过程中的list集合是一个引用,在保存结果时不能保存引用,而应保存引用指向的那个实际对象。
(2)要求的是一个组合,而不是一个排列,可以对进入元素的大小由要求,避免求得重复组合。
时间复杂度即组合数,是O(n ^ k)。空间复杂度即递归深度,是O(k)。
JAVA代码:
public class Solution {
private List<List<Integer>> listList;
public List<List<Integer>> combine(int n, int k) {
listList = new ArrayList<>();
int[] array = new int[n];
for (int i = 0; i < array.length; i++) {
array[i] = i + 1;
}
combine(new ArrayList<>(), array, k);
return listList;
}
private void combine(List<Integer> list, int[] array, int k){
if(list.size() == k){
listList.add(new ArrayList<>(list));
return;
}
for (int i = 0; i < array.length; i++) {
if(list.contains(array[i]) || (!list.isEmpty() && list.get(list.size() - 1) < array[i])){
continue;
}
list.add(array[i]);
combine(list, array, k);
list.remove(list.size() - 1);
}
}
}
LeetCode解题报告: