Leetcode日记：77.组合，回溯问题的优化

问题

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

Example:

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

问题分析

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

个人答案

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，算是相当慢的了，那么如何进行优化呢，下面来看一下大神给的方法。

优化方法

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已满后继续进行迭代，但是这些情况下的迭代都会检测到已满之后立即返回，耗费大量时间。

优化关键代码：

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

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

Leetcode日记：77.组合

2019-03-17
Leetcode
medium