首页 > 编程语言 >190.回溯算法:组合(力扣)

190.回溯算法:组合(力扣)

时间:2024-06-22 11:57:26浏览次数:26  
标签:组合 递归 路径 190 力扣 result 回溯 backtracking

代码随想录 (programmercarl.com)

一、什么是回溯算法

        回溯算法是一种通用的算法设计技巧,特别适用于解决组合、排列、子集等问题。它通过逐步构建解决方案,并在发现部分解决方案无效时撤销(回溯)部分计算,从而寻找所有可能的解决方案。

        回溯算法的基本思想是通过深度优先搜索(DFS)遍历所有可能的解空间,当发现某条路径不符合条件时,返回到上一步,尝试其他路径。

二、回溯法解决的问题

回溯法,一般可以解决如下几种问题:

  • 组合问题:N个数里面按一定规则找出k个数的集合
  • 切割问题:一个字符串按一定规则有几种切割方式
  • 子集问题:一个N个数的集合里有多少符合条件的子集
  • 排列问题:N个数按一定规则全排列,有几种排列方式
  • 棋盘问题:N皇后,解数独等等

三、如何理解回溯法

        回溯法解决的问题都可以抽象为树形结构,因为回溯法解决的都是在集合中递归查找子集,集合的大小就构成了树的宽度,递归的深度就构成了树的深度

递归就要有终止条件,所以必然是一棵高度有限的树(N叉树)。

四、回溯三部曲 

  • 回溯函数模板返回值以及参数
void backtracking(参数)
  • 回溯函数终止条件
if (终止条件) {
    存放结果;
    return;
}
  • 回溯搜索的遍历过程
for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
    处理节点;
    backtracking(路径,选择列表); // 递归
    回溯,撤销处理结果
}

完整模板如下

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
        处理节点;
        backtracking(路径,选择列表); // 递归
        回溯,撤销处理结果
    }
}

力扣题目

 

代码解决 

class Solution {
public:
    vector<vector<int>> result;  // 存储所有组合结果
    vector<int> path;  // 存储当前组合路径

    // 回溯函数
    void backtracking(int n, int k, int index) {
        // 如果当前路径长度等于k,则找到一个有效组合,将其加入结果集
        if (path.size() == k) {
            result.push_back(path);
            return;
        }

        // 从当前索引开始遍历到n
        for (int i = index; i <= n; i++) {
            path.push_back(i);  // 选择当前数加入组合路径
            backtracking(n, k, i + 1);  // 递归调用,继续选择下一个数
            path.pop_back();  // 撤销选择,回溯到上一步
        }
    }

    // 主函数,生成1到n中k个数的所有组合
    vector<vector<int>> combine(int n, int k) {
        backtracking(n, k, 1);  // 从1开始进行回溯
        return result;  // 返回所有组合结果
    }
};

代码使用了回溯算法。主要思路是使用一个递归函数 backtracking 来生成所有可能的组合。在每次递归调用中,我们选择一个数并将其添加到当前组合中,然后递归地继续选择下一个数。如果当前组合的长度达到k,则将其添加到结果集中。在每次递归调用之前,我们通过将当前数从路径中移除来实现回溯。

这里简要解释一下代码的工作流程:

  1. 定义两个全局变量 result 和 path,分别用于存储所有组合结果和当前组合路径。
  2. 定义一个辅助函数 backtracking,它接受三个参数:n(数列的上限)、k(组合中元素的数量)和当前选择的起始索引 index
  3. 如果当前路径长度等于k,则找到了一个有效的组合,将其加入结果集 result
  4. 从当前索引 index 开始遍历到n,对于每个数,将其添加到路径 path 中,然后递归调用 backtracking 函数继续选择下一个数。
  5. 在每次递归调用之前,通过 path.pop_back() 撤销选择,实现回溯。
  6. 在 combine 函数中,调用 backtracking 函数开始生成所有可能的组合,并返回结果集 result

这个算法的时间复杂度是 O(n * k),因为需要生成所有可能的k个数的组合。空间复杂度也是 O(n * k),因为需要存储所有组合和递归调用的栈。

标签:组合,递归,路径,190,力扣,result,回溯,backtracking
From: https://blog.csdn.net/weixin_63779802/article/details/139861583

相关文章

  • 力扣每日一题 6/21 数组
    博客主页:誓则盟约系列专栏:IT竞赛专栏关注博主,后期持续更新系列文章如果有错误感谢请大家批评指出,及时修改感谢大家点赞......
  • 力扣-763. 划分字母区间
    题目地址(763.划分字母区间-力扣(LeetCode))https://leetcode.cn/problems/partition-labels/题目描述给你一个字符串s。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。注意,划分结果需要满足:将所有划分结果按顺序连接,得到的字符串仍然是s。返回......
  • 转:重磅原创)冬之焱: 谈谈Linux内核的栈回溯与妙用
     unwind.c//SPDX-License-Identifier:GPL-2.0-only/**arch/arm/kernel/unwind.c**Copyright(C)2008ARMLimited**StackunwindingsupportforARM**AnARMEABIversionofgccisrequiredtogeneratetheunwind*tables.Forinformationab......
  • 力扣-452. 用最少数量的箭引爆气球
    1.题目介绍题目地址(452.用最少数量的箭引爆气球-力扣(LeetCode))https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/题目描述有一些球形气球贴在一堵用XY平面表示的墙面上。墙面上的气球记录在整数数组 points ,其中points[i]=[xstart,xend]......
  • 力扣每日一题 6/19 排序+动态规划
    博客主页:誓则盟约系列专栏:IT竞赛专栏关注博主,后期持续更新系列文章如果有错误感谢请大家批评指出,及时修改感谢大家点赞......
  • 力扣每日一题 6/17 枚举+双指针
    博客主页:誓则盟约系列专栏:IT竞赛专栏关注博主,后期持续更新系列文章如果有错误感谢请大家批评指出,及时修改感谢大家点赞......
  • 力扣-435.无重叠区间
    1.题目介绍题目地址(435.无重叠区间-力扣(LeetCode))https://leetcode.cn/problems/non-overlapping-intervals/题目描述给定一个区间的集合 intervals ,其中intervals[i]=[starti,endi] 。返回需要移除区间的最小数量,使剩余区间互不重叠 。 示例1:输入:interv......
  • 力扣2713 2024.6.19
    原题网址:此处为链接个人难度评价:1700分析:DP顺序很重要,从大数递推到小数保证了不会每次都是最优子结构而不会有后效性。开了个map来方便二分大于当前数的最小数,状态转移方程显然,记h[x]与l[y]表示第x行小于当前值的最优和第y列小于当前值的最优:dp[x][y]=max(f[x],l[y])注意......
  • N皇后-力扣
    按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n皇后问题研究的是如何将n个皇后放置在n×n的棋盘上,并且使皇后彼此之间不能相互攻击。给你一个整数n,返回所有不同的n皇后问题的解决方案。每一种解法包含一个不同的n皇后问题的......
  • ARMv7 寄存器 工作模式 和指令集 和 堆栈回溯
    因此,在图4-1中,如果处理器是在IRQ模式,我们可以看见R0,R1...R12(与在用户模式看到的相同的寄存器),加上SP_IRQ和LR_IRQ(仅在IRQ模式中可以访问的寄存器)和R15(程序计数器,PC)。我们通常不必指定模式中的寄存器名。如果我们在一行代码中引用R13,处理器会访问当前模式对应的SP寄存器。......