C++力扣题目216--组合求和II

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

216.组合总和III

力扣题目链接(opens new window)

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。

说明:

  • 所有数字都是正整数。
  • 解集不能包含重复的组合。

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

示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]

#思路

本题就是在[1,2,3,4,5,6,7,8,9]这个集合中找到和为n的k个数的组合。

相对于77. 组合 (opens new window),无非就是多了一个限制,本题是要找到和为n的k个数的组合,而整个集合已经是固定的了[1,...,9]。

想到这一点了,做过77. 组合 (opens new window)之后,本题是简单一些了。

本题k相当于树的深度,9(因为整个集合就是9个数)就是树的宽度。

例如 k = 2,n = 4的话,就是在集合[1,2,3,4,5,6,7,8,9]中求 k(个数) = 2, n(和) = 4的组合。

选取过程如图:

C++力扣题目216--组合求和II,算法,数据结构,c++,leetcode

图中,可以看出,只有最后取到集合(1,3)和为4 符合条件。

#回溯三部曲

  • 确定递归函数参数

和77. 组合 (opens new window)一样,依然需要一维数组path来存放符合条件的结果,二维数组result来存放结果集。

这里我依然定义path 和 result为全局变量。

至于为什么取名为path?从上面树形结构中,可以看出,结果其实就是一条根节点到叶子节点的路径。

vector<vector<int>> result; // 存放结果集
vector<int> path; // 符合条件的结果

接下来还需要如下参数:

  • targetSum(int)目标和,也就是题目中的n。
  • k(int)就是题目中要求k个数的集合。
  • sum(int)为已经收集的元素的总和,也就是path里元素的总和。
  • startIndex(int)为下一层for循环搜索的起始位置。

所以代码如下:

vector<vector<int>> result;
vector<int> path;
void backtracking(int targetSum, int k, int sum, int startIndex)

其实这里sum这个参数也可以省略,每次targetSum减去选取的元素数值,然后判断如果targetSum为0了,说明收集到符合条件的结果了,我这里为了直观便于理解,还是加一个sum参数。

还要强调一下,回溯法中递归函数参数很难一次性确定下来,一般先写逻辑,需要啥参数了,填什么参数。

  • 确定终止条件

什么时候终止呢?

在上面已经说了,k其实就已经限制树的深度,因为就取k个元素,树再往下深了没有意义。

所以如果path.size() 和 k相等了,就终止。

如果此时path里收集到的元素和(sum) 和targetSum(就是题目描述的n)相同了,就用result收集当前的结果。

所以 终止代码如下:

if (path.size() == k) {
    if (sum == targetSum) result.push_back(path);
    return; // 如果path.size() == k 但sum != targetSum 直接返回
}
  • 单层搜索过程

本题和77. 组合 (opens new window)区别之一就是集合固定的就是9个数[1,...,9],所以for循环固定i<=9

如图: 

C++力扣题目216--组合求和II,算法,数据结构,c++,leetcode

处理过程就是 path收集每次选取的元素,相当于树型结构里的边,sum来统计path里元素的总和。

代码如下:

for (int i = startIndex; i <= 9; i++) {
    sum += i;
    path.push_back(i);
    backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndex
    sum -= i; // 回溯
    path.pop_back(); // 回溯
}

别忘了处理过程 和 回溯过程是一一对应的,处理有加,回溯就要有减!

参照关于回溯算法,你该了解这些! (opens new window)中的模板,不难写出如下C++代码:

class Solution {
private:
    vector<vector<int>> result; // 存放结果集
    vector<int> path; // 符合条件的结果
    // targetSum:目标和,也就是题目中的n。
    // k:题目中要求k个数的集合。
    // sum:已经收集的元素的总和,也就是path里元素的总和。
    // startIndex:下一层for循环搜索的起始位置。
    void backtracking(int targetSum, int k, int sum, int startIndex) {
        if (path.size() == k) {
            if (sum == targetSum) result.push_back(path);
            return; // 如果path.size() == k 但sum != targetSum 直接返回
        }
        for (int i = startIndex; i <= 9; i++) {
            sum += i; // 处理
            path.push_back(i); // 处理
            backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndex
            sum -= i; // 回溯
            path.pop_back(); // 回溯
        }
    }

public:
    vector<vector<int>> combinationSum3(int k, int n) {
        result.clear(); // 可以不加
        path.clear();   // 可以不加
        backtracking(n, k, 0, 1);
        return result;
    }
};

#剪枝

这道题目,剪枝操作其实是很容易想到了,想必大家看上面的树形图的时候已经想到了。

如图: 

C++力扣题目216--组合求和II,算法,数据结构,c++,leetcode

已选元素总和如果已经大于n(图中数值为4)了,那么往后遍历就没有意义了,直接剪掉。

那么剪枝的地方可以放在递归函数开始的地方,剪枝代码如下:

if (sum > targetSum) { // 剪枝操作
    return;
}

当然这个剪枝也可以放在 调用递归之前,即放在这里,只不过要记得 要回溯操作给做了。

for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) { // 剪枝
    sum += i; // 处理
    path.push_back(i); // 处理
    if (sum > targetSum) { // 剪枝操作
        sum -= i; // 剪枝之前先把回溯做了
        path.pop_back(); // 剪枝之前先把回溯做了
        return;
    }
    backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndex
    sum -= i; // 回溯
    path.pop_back(); // 回溯
}

和回溯算法:组合问题再剪剪枝 (opens new window)一样,for循环的范围也可以剪枝,i <= 9 - (k - path.size()) + 1就可以了。

最后C++代码如下:

class Solution {
private:
    vector<vector<int>> result; // 存放结果集
    vector<int> path; // 符合条件的结果
    void backtracking(int targetSum, int k, int sum, int startIndex) {
        if (sum > targetSum) { // 剪枝操作
            return; 
        }
        if (path.size() == k) {
            if (sum == targetSum) result.push_back(path);
            return; // 如果path.size() == k 但sum != targetSum 直接返回
        }
        for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) { // 剪枝
            sum += i; // 处理
            path.push_back(i); // 处理
            backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndex
            sum -= i; // 回溯
            path.pop_back(); // 回溯
        }
    }

public:
    vector<vector<int>> combinationSum3(int k, int n) {
        result.clear(); // 可以不加
        path.clear();   // 可以不加
        backtracking(n, k, 0, 1);
        return result;
    }
};
  • 时间复杂度: O(n * 2^n)
  • 空间复杂度: O(n)

#总结

开篇就介绍了本题与77.组合 (opens new window)的区别,相对来说加了元素总和的限制,如果做完77.组合 (opens new window)再做本题在合适不过。

分析完区别,依然把问题抽象为树形结构,按照回溯三部曲进行讲解,最后给出剪枝的优化。

相信做完本题,大家对组合问题应该有初步了解了。文章来源地址https://www.toymoban.com/news/detail-797278.html

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

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

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

相关文章

  • Day28 17电话号码的字母组合 39组合求和 40组合求和II

    给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。          因为输入的数字的数量是不确定的,所以for循环的次数也是不确定的,这里就需要用到回溯的方法了。          一般回

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

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

    2024年02月13日
    浏览(42)
  • 【数据结构】回溯算法公式化解题 leetcode经典题目带刷:全排列、组合、子集

    一、什么是回溯算法 回溯算法(Backtracking Algorithm)是一种解决 组合问题 、 排列问题 、 选择问题 等一类问题的常用算法。它通过尝试所有可能的选择来找到问题的解,当发现当前选择不符合要求时,就回溯到之前的状态,然后尝试其他的选择。 1、基本思想: 从问题的起

    2024年02月11日
    浏览(45)
  • DAY25:回溯算法组合题216、17

    经过了昨天组合的题目的学习,这道题比较简单,套用之前的模板就可以 基本思路 终止条件,遇到向量的个数一样,并且sum等于n的时候终止。 输入变量,n,k,还有起始的idx和基于当前元素之和的sum 逻辑就是,按照循环递归下去,注意要对sum值进行回溯。 时间复杂度O(n *

    2024年01月20日
    浏览(37)
  • leetcode216. 组合总和 III(回溯算法-java)

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

    2024年02月10日
    浏览(45)
  • 力扣:40. 组合总和 II

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

    2024年02月21日
    浏览(34)
  • 40. 组合总和 II - 力扣(LeetCode)

    题目描述 给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意:解集不能包含重复的组合。 输入示例 输出示例 解题代码

    2024年01月23日
    浏览(39)
  • 【数据结构与算法系列5】螺旋矩阵II (C++ & Python)

    给你一个正整数 n ,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。 示例 1: 示例 2: 提示: 1 = n = 20 使用和二分法一样的思想,确定循环不变量,确定是左闭右开,还是左闭右闭合,本次使用的是左闭右开 C++ 实现: python 实现:

    2024年02月09日
    浏览(41)
  • 力扣67. 二进制求和算法

    这道题需要,给你两个字符串比如 答案是:\\\"10101\\\" 然后需要你给出计算结果,那么我们很容易想到两种做法 1. 调库做法:直接转化为整数,然后用内置函数做进制转换直接计算出结果 2. 计算做法:将十进制思维移植过来,对每一位加并且做carry操作,最后得出结果 笔者最初

    2024年01月16日
    浏览(45)
  • 代碼隨想錄算法訓練營|第四十六天|完全背包、518. 零钱兑换 II、377. 组合总和 Ⅳ。刷题心得(c++)

    目录 动态规划 - 完全背包 和01背包的差別 定義 核心代碼 遍歷順序 總結 讀題 518. 零钱兑换 II 自己看到题目的第一想法 看完代码随想录之后的想法 377. 组合总和 Ⅳ 自己看到题目的第一想法 518. 零钱兑换 II - 實作 思路 Code 377. 组合总和 Ⅳ - 實作 思路 Code 總結 自己实现过

    2024年02月08日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包