7.1组合及其优化(LC77-M)

2023-12-21 22:35:51

算法:

第一次取1 2 3 4
取1时,留下234

取2时,留下34

取3时,留下4

取4时,留下null


接着继续取234中的2,与1组合,得到12

取234中的3,与1组合,得到13

取234中的4,与1组合,得到14


接着继续取34中的3,与2组合,得到23

取34中的4,与2组合,得到24


接着继续取4,与3组合,得到34


回溯三部曲:

1.确定函数返回值和参数:返回值是void;参数:n、k(题目中都给出了),还要一个startindex,因为每次递归的时候,怎么知道从哪里开始取呢?这时候就需要一个index指引一下。

2.确定终止条件:当取到一个组合时,单层逻辑终止,比如取到12,就不会往下了;因为每个组合(12 13 14 23 24 34)都是树的叶子结点

3.单层递归逻辑:也就是单层搜索的逻辑。在这里就是for循环。

在for循环中,push入要取的数值1或2或3或4;

调用递归

回溯:撤销结果。pop

调试过程:

定义全局变量:result为二维数组,path为一维数组

数组List,用ArrayList和LinkedList都可以

class Solution {
//全局变量
    List<List<Integer>>result = new ArrayList();
    LinkedList<Integer>path = new LinkedList();
    public List<List<Integer>> combine(int n, int k) {
        backtracking(n,k,1);
        return result;
    }
    void backtracking (int n, int k, int startindex){
        if (path.size()==k){
            result.add(path);
            return;
        }
        for(int i=startindex;i<=n;i++){
            path.add(i);
            backtracking(n,k,i+1);//往二叉树的深处递归,所以是i+1
            path.pop();
        }
    }
}

原因:输出都是空集

问题出在?`result.add(path);`?这一行以及?`path.pop();`?上

调用?`result.add(path);`?时,实际上是将?`path`?对象的引用加入了?`result`?中,而不是?`path`?对象的拷贝。随后对?`path`?对象的任何修改都会影响到?`result`?中的元素。

`path`?在递归过程中被修改了多次,但是?`result`?中存储的都是同一个?`path`?对象的引用,因此最终?`result`?中的所有元素都指向了同一个?`path`?对象。

可以在将?`path`?加入?`result`?前,先创建一个?`path`?的拷贝,然后将拷贝加入?`result`。在 Java 中,可以通过?`new LinkedList<>(path)`?来创建?`path`?的拷贝另外,`path.pop()`?应该改为?`path.removeLast()`,因为 Java 中的?`LinkedList`?类使用?`removeLast`?来移除最后一个元素。

正确代码:

class Solution {
//全局变量
    List<List<Integer>>result = new ArrayList();
    LinkedList<Integer>path = new LinkedList();
    public List<List<Integer>> combine(int n, int k) {
        backtracking(n,k,1);
        return result;
    }
    void backtracking (int n, int k, int startindex){
        if (path.size()==k){
            result.add(new LinkedList<>(path));
            return;
        }
        for(int i=startindex;i<=n;i++){
            path.add(i);
            backtracking(n,k,i+1);//往二叉树的深处递归,所以是i+1
            path.removeLast();
        }
    }
}

剪枝优化

回溯法虽然是暴力搜索,但也有时候可以有点剪枝优化一下的。

只要改一下for循环的条件即可

来举一个例子,n = 4,k = 4的话,答案显然是[1,2,3,4]

如果像刚刚一样求,会增加很多不必要的循环:

那么第一层for循环的时候,从元素2开始的遍历都没有意义了。 在第二层for循环,从元素3开始的遍历都没有意义了。

剪枝:

缩小for循环的范围

  1. 已经选择的元素个数:path.size();

  2. 所需需要的元素个数为: k - path.size();

  3. 列表中剩余元素 >= 所需需要的元素个数

    1. n-i?>=k - path.size()

  4. 在集合n中至多要从该起始位置 : i <= n - (k - path.size()) + 1,开始遍历

    1. 为什么有个+1呢,因为包括起始位置,我们要是一个左闭的集合。

剪枝优化后的正确代码:

class Solution {
//全局变量
    List<List<Integer>>result = new ArrayList();
    LinkedList<Integer>path = new LinkedList();
    public List<List<Integer>> combine(int n, int k) {
        backtracking(n,k,1);
        return result;
    }
    void backtracking (int n, int k, int startindex){
        if (path.size()==k){
            result.add(new LinkedList<>(path));
            return;
        }
        for(int i=startindex; i <= n - (k - path.size())+1;i++){
            path.add(i);
            backtracking(n,k,i+1);//往二叉树的深处递归,所以是i+1
            path.removeLast();
        }
    }
}

文章来源:https://blog.csdn.net/m0_50696252/article/details/135078408
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。