每日刷题|回溯法解决组合问题

这篇具有很好参考价值的文章主要介绍了每日刷题|回溯法解决组合问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

每日刷题|回溯法解决组合问题,刷题  打怪历练,算法,c++,开发语言,leetcode

                                        食用指南:本文为作者刷题中认为有必要记录的题目

                                       ♈️今日夜电波:保留—郭顶

                                                                1:33 ━━━━━━️💟──────── 4:30
                                                                    🔄   ◀️   ⏸   ▶️    ☰ 

                                      💗关注👍点赞🙌收藏您的每一次鼓励都是对我莫大的支持😍 


目录

什么是回溯法?

回溯法用在何处?

        

回溯法的理解

🌸一、组合

💮二、组合总和

🌺三、组合总和II


什么是回溯法?

        回溯法的实现方式是通过递归函数来实现的,每次递归时都会考虑一种可能的解,并判断这种解是否符合要求。如果符合要求,就返回这个解;如果不符合要求,就回溯到上一步,尝试另一种可能的解。回溯算法常用于求解组合、排列、子集等问题,例如八皇后问题、数独等。回溯算法的时间复杂度通常比较高,因为需要枚举所有可能的解,所以在实际应用中需要考虑优化算法。

回溯法用在何处?

回溯法通常用于解决以下问题:

1. 生成所有的排列或组合。

2. 解决搜索问题,如迷宫问题、数独问题、八皇后问题等。

3. 解决决策问题,如0-1背包问题、旅行商问题等。

4. 解决图论问题,如最小生成树问题、哈密尔顿回路问题等。

在这些问题中,回溯法一般通过深度优先搜索的方式遍历所有的可能性,直到找到符合条件的解或搜索到所有可能性。

        

回溯法的理解
 

        本文参考了一位大佬的题解,详细的介绍了回溯法:链接

        记住一句话:for循环横向遍历,递归纵向遍历,回溯不断调整结果集。 这句话将从始至终贯穿我们对于以上问题的回溯解决办法。


🌸一、组合

题目链接:77. 组合

题目描述:

        给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。

        你可以按 任何顺序 返回答案。

示例 1:

输入:n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2:

输入:n = 1, k = 1
输出:[[1]]

提示:

  • 1 <= n <= 20
  • 1 <= k <= n

 本题思路:

        采用经典的“回溯三部曲”:

        1、定义两个全局变量,一个用来存放符合条件单一结果(path),一个用来存放符合条件结果的集合(result)。注意要记得用一个变量来记录遍历的位置。

        2、回溯的主体,回溯终止条件。path保存一组数据,每次遍历到叶子节点,再插入到result中,并且回溯到上一个节点。

        3、单层搜索的过程。for循环用来横向遍历,递归的过程是纵向遍历。

一图流:(以n=4,k=3为例)

每日刷题|回溯法解决组合问题,刷题  打怪历练,算法,c++,开发语言,leetcode

class Solution {
public:
    vector<vector<int>> rtu;
    vector<int> path;
    void backtrack(int n,int k,int index)
    {
        if(path.size()==k)//结束条件
        {
            rtu.push_back(path);
            return;
        }
        for(int i=index;i<=n;i++)//横向遍历
        {
            path.push_back(i);
            backtrack(n,k,i+1);//纵向递归
            path.pop_back();//回溯
        }
    }
public:
    vector<vector<int>> combine(int n, int k) {
        backtrack(n,k,1);
        return rtu;
    }
};

加入剪枝优化:

class Solution {
public:
    vector<vector<int>> rtu;
    vector<int> path;
    void backtrack(int n,int k,int index)
    {
        if(path.size()==k)//结束条件
        {
            rtu.push_back(path);
            return;
        }
        for(int i=index;i<=n-(k-path.size())+1;i++)//横向遍历
        {
            path.push_back(i);
            backtrack(n,k,i+1);//纵向递归
            path.pop_back();//回溯
        }
    }
public:
    vector<vector<int>> combine(int n, int k) {
        backtrack(n,k,1);
        return rtu;
    }
};

💮二、组合总和

题目链接:39. 组合总和

题目描述:

        给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。

  candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。 

        对于给定的输入,保证和为 target 的不同组合数少于 150 个。

示例 1:

输入:candidates = [2,3,6,7], target = 7

输出:[[2,2,3],[7]]
解释:
2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选, 7 = 7 。
仅有这两种组合。

示例 2:

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3:

输入: candidates = [2], target = 1
输出: []

提示:
  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • candidates 的所有元素 互不相同
  • 1 <= target <= 40

 本题思路:

        同样采用经典的“回溯三部曲”,但是做了些许改变。相较于上一题,在这里不需要对于index进行+1操作,跳出循环条件改为对target的两次判断。增加一个变量用于记录总和。

class Solution {
public:
vector<int> path;
vector<vector<int>> rtu;
void backtrack(vector<int>& candidates,int target,int index,int sum)
{
    if(target==sum)
    {
        rtu.push_back(path);
        return;
    }
    if(sum>target)
    {
        return;
    }
    for(int i=index;i<candidates.size();i++)
    {
        sum+=candidates[i];
        path.push_back(candidates[i]);
        backtrack(candidates,target,i,sum);
        path.pop_back();
        sum-=candidates[i];
    }
}
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        rtu.clear();
        path.clear();
        backtrack(candidates,target,0,0);
        return rtu;
    }
};

 加入剪枝优化:

class Solution {
public:
vector<int> path;
vector<vector<int>> rtu;
void backtrack(vector<int>& candidates,int target,int index,int sum)
{
    if(target==sum)
    {
        rtu.push_back(path);
        return;
    }
    if(sum>target)
    {
        return;
    }
    for(int i=index;i<candidates.size()&&sum + candidates[i] <= target;i++)
    {
        sum+=candidates[i];
        path.push_back(candidates[i]);
        backtrack(candidates,target,i,sum);
        path.pop_back();
        sum-=candidates[i];
    }
}
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        rtu.clear();
        path.clear();
        sort(candidates.begin(),candidates.end());
        backtrack(candidates,target,0,0);
        return rtu;
    }
};

🌺三、组合总和II

题目链接:40. 组合总和 II

 题目描述:

        给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

   candidates 中的每个数字在每个组合中只能使用 一次 。

        注意:解集不能包含重复的组合。 

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5
输出:
[
[1,2,2],
[5]
]

提示:

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30

  本题思路:

        这里相较于上一题主要的变动为去重的操作:

        如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false,就说明:前一个树枝,使用了candidates[i - 1],也就是说同一树层使用过candidates[i - 1]。基于以上再加入剪枝操作就可以完成去重的操作了!与此相对的还要对for循环加入continue操作。

class Solution {
public:
vector<int> path;
vector<vector<int>> rtu;
void backtrack(vector<int>& candidates, int target,int num,int index,vector<bool>& used)
{
    if(target==num)
    {
        rtu.push_back(path);
        return;
    }
    for(int i=index;i<candidates.size()&&num+candidates[i]<=target;i++)
    {
        if(i>0&&candidates[i]==candidates[i-1]&&used[i-1]==false)
        continue;
        num+=candidates[i];
        path.push_back(candidates[i]);
        used[i]=1;
        backtrack(candidates,target,num,i+1,used);
        num-=candidates[i];
        path.pop_back();
        used[i]=0;
    }
}
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<bool> used(candidates.size(), false);
        path.clear();
        rtu.clear();
        sort(candidates.begin(),candidates.end());
        backtrack(candidates,target,0,0,used);
        return rtu;
    }
};

                感谢你耐心的看到这里ღ( ´・ᴗ・` )比心,如有哪里有错误请踢一脚作者o(╥﹏╥)o!  

                                每日刷题|回溯法解决组合问题,刷题  打怪历练,算法,c++,开发语言,leetcode 

                                                                 给个三连再走嘛~      文章来源地址https://www.toymoban.com/news/detail-731745.html

到了这里,关于每日刷题|回溯法解决组合问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C/C++练习】经典的排列组合问题(回溯算法)——电话号码的字母组合

    📖题目描述 题目出处 :电话号码的字母组合 示例: 📖题解  这是一道典型的排列组合问题,根据输入,我们需要找到所有的组合。下面以输入字符串 digits = \\\"23\\\" 为例来讲解这道题目。 图解: 分析:  首先要知道输入的字符串 \\\"23\\\" 中的数字字符分别对应哪些字符串,其中

    2024年02月16日
    浏览(40)
  • 代码随想录Day20 回溯算法 LeetCode77 组合问题

    以下内容更详细解释来自于:代码随想录 (programmercarl.com) 回溯法也叫回溯搜索法,是搜索法的一种,我们之前在二叉树中也经常使用到回溯来解决问题,其实 有递归就有回溯 ,有的时候回溯隐藏在递归之下,我们不容易发觉,今天我们来详细介绍一下什么是回溯,它能解决哪些问题.

    2024年02月08日
    浏览(54)
  • (3)回溯算法团灭子集、组合、排列问题 -- 元素无重可复选

    回溯算法团灭子集、组合、排列问题 根据元素是否重复和是否可复选,分为以下三种变体: 1、元素无重不可复选 2、元素有重不可复选 3、元素无重可复选 该篇给出第三种情况的代码,另外两种的实现见上方变体链接。

    2024年02月09日
    浏览(31)
  • 每日OJ题_DFS回溯剪枝⑨_力扣39. 组合总和(两种思路)

    目录 力扣39. 组合总和 解析代码1 解析代码2 39. 组合总和 LCR 081. 组合总和 难度 中等 给你一个  无重复元素  的整数数组  candidates  和一个目标整数  target  ,找出  candidates  中可以使数字和为目标数  target  的 所有   不同组合  ,并以列表形式返回。你可以按  任意顺序

    2024年04月28日
    浏览(33)
  • 力扣算法刷题Day44|动态规划:完全背包问题 零钱兑换II 组合总和Ⅳ

    力扣题目:#518.零钱兑换II(完全背包组合问题) 刷题时长:7min 解题方法:动态规划(完全背包) 复杂度分析 时间复杂度: O(mn),其中 m 是amount,n 是 coins 的长度 空间复杂度: O(m) 问题总结 对递推公式的理解 本题收获 题意转换:纯完全背包是凑成背包最大价值是多少,而本

    2024年02月13日
    浏览(42)
  • 【回溯算法】77. 组合

    回溯结束条件 track长度等于k 然后收集当前的路径 遍历所有的节点 然后选择当前节点 通过start参数控制遍历 避免产生重复的子集 移除当前的选择

    2024年02月09日
    浏览(38)
  • 算法套路十一 ——回溯法之组合型回溯

    该节是在上一节回溯法之子集型回溯的基础上进行描写,组合型回溯会在子集型回溯的基础上判断所选子集是否符合组合要求, 故请首先阅读上一节算法套路十——回溯法之子集型回溯 给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按 任何顺序 返

    2023年04月22日
    浏览(40)
  • 算法:回溯算法(以解决n皇后问题为例)

    基本思想:回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。八皇后问题就是回溯算法的典型,第一步按照顺序放一个皇后,然后第二步符合要求放第2个皇后,如果没有位置符合要求,那么就要改变第一个皇后的位置,重新放第2个皇后

    2024年02月05日
    浏览(32)
  • leetcode77. 组合(回溯算法-java)

    来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/combinations 给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 示例 1: 输入:n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] 示例 2: 输入:n = 1, k = 1 输出:[[1]] 提示:

    2024年02月11日
    浏览(54)
  • day24 | 回溯算法基础、77. 组合

    目录: 回溯法理论基础 https://programmercarl.com/回溯算法理论基础.html#题目分类大纲如下 回溯法,一般可以解决如下几种问题: 组合问题:N个数里面按一定规则找出k个数的集合 切割问题:一个字符串按一定规则有几种切割方式 子集问题:一个N个数的集合里有多少符合条件的

    2024年02月11日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包