Day 24 回溯算法01

作者：知新_RL | 2024-03-25 01:45:14

踩

Day 24 回溯算法01

理论基础

回溯和递归相辅相成，有有递归就会有回溯，通常在递归函数的下面

回溯法解决的问题：

1.组合问题。在一个集合中找到指定的组合（子集）

2.切割问题。给一个字符串，如何切割满足特定条件

3.子集问题。子集列举

4.排列组合问题，组合没有顺序，排列强调顺序

5.棋盘问题，n皇后，解数独

回溯法的理解：回溯法可以抽象为一个树，树的宽度相当于集合大小，树的深度等于递归深度


void 函数名（参数）{
    if(终止条件）{ 收集结果; return}
    for(集合元素集）{
        处理节点；
        递归函数;
        回溯操作(撤销递归导致的操作）;
    }
    return;

77. 组合

题目链接：77. 组合 - 力扣（LeetCode）

思路：回溯三步走，套用上面的模板，要设置公共参数。

使用LinkedList ，与 ArrayList 相比，LinkedList 的增加和删除的操作效率更高，而查找和修改的操作效率较低。

其中LinkedList 转化为ArraryList 使用的是构造方法


class Solution {
    List<List<Integer>> reuslt = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        combine1(n,k,1);
        return reuslt;
    }
 
    public void combine1(int n, int k, int start){
        if(path.size() == k){
            reuslt.add(new ArrayList<>(path));//构造方法进行类型转换
            return;
        }
        for(int i = start; i <= n; i++){
            path.add(i);
            combine1(n,k,i+1);
            path.removeLast();
        }
    }
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/306171