力扣第40题 组合总和 || c++ 回溯经典

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

题目

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

思路和解题方法

  1. 首先定义了一个二维向量ans用于存储所有满足条件的组合结果,以及一个一维向量path用于存储当前路径。
  2. 定义了一个backtracking函数,该函数通过递归的方式进行回溯操作。参数包括:候选元素数组candidates,目标值target,当前路径和sum,开始索引startindex,以及一个布尔型向量used用于标记元素是否被使用过。
  3. backtracking函数中,首先判断当前路径和是否等于目标值,如果等于,则将该路径添加到结果中,并返回。
  4. 然后通过一个循环遍历候选元素数组,从开始索引startindex开始遍历。在遍历过程中,如果遇到重复的元素且前一个元素未被使用过,则跳过当前元素,以避免生成重复的组合。
  5. 对于每个满足条件的元素,将其加入路径中,并将其标记为已使用。然后递归调用backtracking函数,进入下一层,更新参数:目标值为target减去当前元素,当前路径和为sum加上当前元素,起始索引为当前元素的下一个位置,以及更新了使用状态的布尔型向量used
  6. 当递归返回时,表示已经找到了所有满足条件的组合,需要进行回溯操作。即将当前元素的状态重置为未使用,将路径和减去当前元素,以及移除路径中的当前元素。
  7. 最后,在主函数combinationSum2中,首先定义一个布尔型向量used用于标记元素是否被使用过,并清空路径和结果向量。然后对候选元素数组进行排序,以便在回溯过程中剪枝操作。最后,调用backtracking函数开始解决问题,并返回结果向量ans

复杂度

        时间复杂度:

                O(2^n * n)

        在回溯算法中,每个元素都有两种选择:选择当前元素或者不选择当前元素。因此,在最坏情况下,需要遍历所有可能的组合,这样的组合总数为2^n。而在每个组合中,需要花费线性的时间将路径添加到结果中,因此乘以n。

        空间复杂度

                O(n)

        空间复杂度方面,使用了ans、path和used三个额外的数据结构来辅助求解。其中ans和path的空间复杂度为O(n),used的空间复杂度也为O(n)。因此,整体的空间复杂度为O(n)。

c++ 代码

class Solution {
public:
    vector<vector<int>> ans; // 用于存储结果的二维向量
    vector<int> path; // 用于存储当前路径的一维向量

    void backtracking(vector<int> candidates, int target, int sum, int startindex, vector<bool> used) {
        if (sum == target) { // 当路径和等于目标值时,将当前路径添加到结果中
            ans.push_back(path);
            return;
        }

        for (int i = startindex; i < candidates.size() && sum + candidates[i] <= target; i++) {
            if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
                continue; // 遇到重复的元素,并且前一个元素未被使用过,则跳过当前元素
            }

            sum += candidates[i]; // 加上当前元素
            path.push_back(candidates[i]); // 将当前元素添加到路径中
            used[i] = true; // 标记当前元素已被使用
            backtracking(candidates, target, sum, i + 1, used); // 递归调用下一层,startIndex为i+1,表示下一个元素
            used[i] = false; // 回溯,将当前元素重置为未使用状态
            sum -= candidates[i]; // 回溯,减去当前元素
            path.pop_back(); // 回溯,移除当前元素
        }
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<bool> used(candidates.size(), false); // 用于标记元素是否被使用过的向量
        path.clear(); // 清空路径向量
        ans.clear(); // 清空结果向量
        sort(candidates.begin(), candidates.end()); // 对候选元素进行排序
        backtracking(candidates, target, 0, 0, used); // 调用回溯函数
        return ans; // 返回结果向量
    }
};

c++优化代码

  1. 首先,在主函数combinationSum2中,对候选元素数组进行排序,以确保相同的元素都挨在一起。这样做的目的是为了在回溯过程中剪枝,避免生成重复的组合。

  2. 在回溯函数backtracking中,通过判断当前元素是否和前一个元素相同来决定是否跳过该元素。如果当前元素和前一个元素相同且前一个元素未被使用过,则跳过当前元素。这样可以避免在同一树层重复使用相同的元素,从而避免生成重复的组合。

  3. 另外,这个版本的代码还有一个区别是每个数字在每个组合中只能使用一次。这通过在递归调用中将起始索引startIndex设为i + 1来实现。

class Solution {
private:
    vector<vector<int>> result; // 保存最终的结果
    vector<int> path; // 保存当前的组合路径

    void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
        if (sum == target) { // 如果组合的和等于目标值,则将当前路径加入结果集
            result.push_back(path);
            return;
        }

        for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
            if (i > startIndex && candidates[i] == candidates[i - 1]) { // 剪枝操作,防止生成重复组合
                continue; // 当前元素和前一个元素相同,且前一个元素未被使用过,则跳过当前元素
            }

            sum += candidates[i]; // 将当前元素加入组合和中
            path.push_back(candidates[i]); // 将当前元素加入组合路径中
            backtracking(candidates, target, sum, i + 1); // 递归调用,起始索引为i+1,保证每个元素在每个组合中只能使用一次
            sum -= candidates[i]; // 回溯,将当前元素从组合和中去除
            path.pop_back(); // 回溯,将当前元素从组合路径中去除
        }
    }

public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        path.clear(); // 清空路径
        result.clear(); // 清空结果集

        sort(candidates.begin(), candidates.end()); // 对候选元素数组进行排序,确保相同元素挨在一起
        backtracking(candidates, target, 0, 0); // 进行回溯操作,得到符合条件的组合

        return result; // 返回最终的结果
    }
};

觉得有用的话可以点点赞,支持一下。

如果愿意的话关注一下。会对你有更多的帮助。

每天都会不定时更新哦  >人<  。文章来源地址https://www.toymoban.com/news/detail-724117.html

到了这里,关于力扣第40题 组合总和 || c++ 回溯经典的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 力扣:40. 组合总和 II

    回溯: 1.先声明好大集合和小集合,在调用回溯函数,终止条件为sum==target,要进行剪枝操作减少遍历的次数,去重操作防止数组中有两个相同的值来组成的集合相同。

    2024年02月21日
    浏览(34)
  • LeetCode 39. 组合总和(回溯+剪枝)

    链接:LeetCode 39. 组合总和 难度:中等 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。 candidates 中的 同一个 数字可以 无限制重复被选

    2024年02月14日
    浏览(45)
  • 力扣日记1.22-【回溯算法篇】216. 组合总和 III

    日期:2023.1.22 参考:代码随想录、力扣 题目描述 难度:中等 找出所有相加之和为 n 的 k 个数的组合,且满足下列条件: 只使用数字1到9 每个数字 最多使用一次 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。 示例 1: 输入:

    2024年01月23日
    浏览(43)
  • 【LeetCode-中等题】40. 组合总和 II

    本题需要注意的就是去重操作因为nums数组里面的元素可能存在重复: 不重复的版本:【LeetCode-中等题】39. 组合总和 不去重版 参考讲解视频—回溯算法中的去重,树层去重树枝去重,你弄清楚了没?| LeetCode:40.组合总和II

    2024年02月09日
    浏览(38)
  • leetcode216. 组合总和 III(回溯算法-java)

    来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/combination-sum-iii 找出所有相加之和为 n 的 k 个数的组合,且满足下列条件: 只使用数字1到9 每个数字 最多使用一次 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。 示例 1: 输

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

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

    2024年04月28日
    浏览(32)
  • LeetCode刷题13:回溯+剪枝解决216.组合总和 III

    找出所有相加之和为  n   的  k   个数的组合,且满足下列条件: 只使用数字1到9 每个数字  最多使用一次   返回  所有可能的有效组合的列表  。该列表不能包含相同的组合两次,组合可以以任何顺序返回。 示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]] 解释: 1 + 2 + 4 = 7 没有其他

    2024年02月02日
    浏览(44)
  • LeetCode(力扣)39. 组合总和Python

    https://leetcode.cn/problems/combination-sum/description/

    2024年02月09日
    浏览(35)
  • 力扣第131题 分割回文串 c++ 回溯+简单 动态规划(是否为回文子串)

    131. 分割回文串 中等 相关标签 字符串   动态规划   回溯 给你一个字符串  s ,请你将   s   分割成一些子串,使每个子串都是  回文串  。返回  s  所有可能的分割方案。 回文串  是正着读和反着读都一样的字符串。 示例 1: 示例 2: 提示: 1 = s.length = 16 s  仅由小写

    2024年02月07日
    浏览(46)
  • 【算法】递归、回溯、剪枝、dfs 算法题练习(组合、排列、总和问题;C++)

    后面的练习是接着下面链接中的文章所继续的,在对后面的题练习之前,可以先将下面的的文章进行了解👇: 【算法】{画决策树 + dfs + 递归 + 回溯 + 剪枝} 解决排列、子集问题(C++) 思路 题意分析 :要求根据给出的数字,算出合法的括号组成个数。根据题目,我们可以总

    2024年02月22日
    浏览(50)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包