Leetcode日记:77.组合,回溯问题的优化

问题

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

Example:

1
2
3
4
5
6
7
8
9
10
Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

问题分析

给定一个数字n,给定一个数量k,求1-n中k个数的组合。
标准的回溯问题,下面直接看代码,这道题是让我们看看如何优化回溯问题的代码。

个人答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> list = new ArrayList<>();
backtrack(list, new ArrayList<>(), n, k, 1);
return list;
}

private void backtrack(List<List<Integer>> list , List<Integer> tempList, int n,int k, int start){
if(tempList.size()==k){
list.add(new ArrayList<>(tempList));
}
else{
for(int i = start; i <=n ;i++){
tempList.add(i);
backtrack(list, tempList, n,k, i + 1);
tempList.remove(tempList.size() - 1);
}
}
}

思路和之前的回溯都是一样的,效果是运行时间42ms,算是相当慢的了,那么如何进行优化呢,下面来看一下大神给的方法。

优化方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> list = new LinkedList<>();
backtrack(list,n,k,1,new ArrayList<Integer>());
return list;
}
private void backtrack(List<List<Integer>> list, int n, int k, int start, List<Integer> tempList){
if(k==0) {
list.add(new LinkedList<>(tempList));
return;
}
for(int i = start;i<=n-k+1;i++){
tempList.add(i);
backtrack(list,n,k-1,i+1,tempList);
tempList.remove(tempList.size()-1);
}
}

社区大神给出的解决方法与我的很类似,毕竟都是经典回溯代码,差不太多,那么,优化后的方法耗时多长时间呢?

答案是2ms

足以见得优化的重要性,当我们编写leetcode时候,不仅要关注算法的准确,对于算法的复杂度、内存的分析优化往往更能提高我们的编程技巧,对以后的发展会很有帮助。

废话不多说,我们来看一下42ms和2ms在思路代码上的区别:

优化分析

主要区别在于进行迭代的时候,每次递归我的方法传入的是k个数,其实我们知道,当进行一次递归后,我们只需要添加k-1个数就好,因为在这之前必定有一个数已经被添加,而我并没有考虑到这一优化情况。我的循环会在数组tempList已满后继续进行迭代,但是这些情况下的迭代都会检测到已满之后立即返回,耗费大量时间。

优化关键代码:

  1. 循环中的i<=n-k+1判断条件
  2. 迭代中随着迭代层数不断变换带入的k-1

归纳起来,便是一点:
当进行递归深入时,确定好进行迭代的量,判断好哪些变量需要根据递归深度增加而变化,避免循环固定化、冗余化。

更多回溯算法

更多关于回溯算法的问题请转到回溯算法标签