LeetCode216:组合总和Ⅲ

2024-04-20 19:20
文章标签 组合 总和 leetcode216

本文主要是介绍LeetCode216:组合总和Ⅲ,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述
找出所有相加之和为 n 的 k 个数的组合,且满足下列条件:

只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。

在这里插入图片描述
解题思想
使用回溯算法

代码

class Solution {
public:vector<vector<int>> res;vector<int> path;int sum = 0;void backTracking(int n,int k,int startIndex) {if (path.size() == k && sum == n) {res.push_back(path);return;}for (int i = startIndex; i <= 9; i++) {sum += i;path.push_back(i);//往下走 i+1backTracking(n, k, i+1);//回溯path.pop_back();sum -= i;}}vector<vector<int>> combinationSum3(int k, int n) {backTracking(n, k, 1);return res;}
};

使用剪枝优化

class Solution {
public:vector<vector<int>> res;vector<int> path;int sum = 0;void backTracking(int n, int k, int startIndex) {//优化:在深度上进行剪枝操作if (sum > n) return;if (path.size() == k && sum == n) {res.push_back(path);return;}//优化:在宽度上进行剪枝操作  9-(k-path.size())+1for (int i = startIndex; i <= 9-(k-path.size())+1; i++) {sum += i;path.push_back(i);//往下走 i+1backTracking(n, k, i + 1);//回溯path.pop_back();sum -= i;}}vector<vector<int>> combinationSum3(int k, int n) {backTracking(n, k, 1);return res;}
};

这篇关于LeetCode216:组合总和Ⅲ的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/921111

相关文章

hdu4869(逆元+求组合数)

//输入n,m,n表示翻牌的次数,m表示牌的数目,求经过n次操作后共有几种状态#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#includ

Go组合

摘要 golang并非完全面向对象的程序语言,为了实现面向对象的继承这一神奇的功能,golang允许struct间使用匿名引入的方式实现对象属性方法的组合 组合使用注意项 使用匿名引入的方式来组合其他struct 默认优先调用外层方法 可以指定匿名struct以调用内层方法 代码 package mainimport ("fmt")type People struct{}type Pe

组合c(m,n)的计算方法

问题:求解组合数C(n,m),即从n个相同物品中取出m个的方案数,由于结果可能非常大,对结果模10007即可。       共四种方案。ps:注意使用限制。 方案1: 暴力求解,C(n,m)=n*(n-1)*...*(n-m+1)/m!,n<=15 ; int Combination(int n, int m) { const int M = 10007; int

代码随想录训练营day37|52. 携带研究材料,518.零钱兑换II,377. 组合总和 Ⅳ,70. 爬楼梯

52. 携带研究材料 这是一个完全背包问题,就是每个物品可以无限放。 在一维滚动数组的时候规定了遍历顺序是要从后往前的,就是因为不能多次放物体。 所以这里能多次放物体只需要把遍历顺序改改就好了 # include<iostream># include<vector>using namespace std;int main(){int n,m;cin>>n>>m;std::vector<i

INDEX+SMALL+IF+ROW函数组合使用解…

很多人在Excel中用函数公式做查询的时候,都必然会遇到的一个大问题,那就是一对多的查找/查询公式应该怎么写?大多数人都是从VLOOKUP、INDEX+MATCH中入门的,纵然你把全部的多条件查找方法都学会了而且运用娴熟,如VLOOKUP和&、SUMPRODUCT、LOOKUP(1,0/....,但仍然只能对这种一对多的查询望洋兴叹。   这里讲的INDEX+SMALL+IF+ROW的函数组合,

代码随想录算法训练营Day37|完全背包问题、518.零钱兑换II、377. 组合总和 Ⅳ、70. 爬楼梯(进阶版)

完全背包问题                  和01背包最大区别就是一个物品可以重复放多次,因此遍历空间时可以从前往后。 import java.util.*;public class Main{public static void main (String[] args) {Scanner sc = new Scanner(System.in);int m = sc.nextInt

【内网】ICMP出网ew+pingtunnel组合建立socks5隧道

❤️博客主页: iknow181 🔥系列专栏: 网络安全、 Python、JavaSE、JavaWeb、CCNP 🎉欢迎大家点赞👍收藏⭐评论✍ 通过环境搭建,满足以下条件: 攻击机模拟公网vps地址,WEB边界服务器(Windows Server 2008)模拟公司对外提供Web服务的机器,该机器可以通内网,同时向公网提供服务。内网同网段存在一台Windows内网服务

PyPortfolioOpt:Python中的投资组合优化工具

PyPortfolioOpt:Python中的投资组合优化工具 在金融领域,投资组合优化是一个关键的环节,它帮助投资者在追求最大回报的同时管理风险。今天,我们将探索一个名为PyPortfolioOpt的Python库,它提供了一系列的工具和算法,用于构建和优化投资组合。 概览 PyPortfolioOpt是一个开源的Python库,专门用于金融投资组合的优化。它包括经典的有效前沿、Black

读软件设计的要素03概念的组合

1. 概念的组合 1.1. 概念不像程序那样,可以用较大的包含较小的 1.1.1. 每个概念对用户来说都是平等的,软件或系统就是一组串联运行的概念组合 1.2. 概念是通过操作来同步组合的 1.2.1. 同步并不增加新的概念操作,但会限制已有的操作,从而消除一些独立概念可能会出现的操作序列 1.3. 在自由组合中,概念彼此独立,仅受一些记录的约束,这些约束是为了确保概念对事物观点的一

java设计模式day03--(结构型模式:代理模式、适配器模式、装饰者模式、桥接模式、外观模式、组合模式、享元模式)

5,结构型模式 结构型模式描述如何将类或对象按某种布局组成更大的结构。它分为类结构型模式和对象结构型模式,前者采用继承机制来组织接口和类,后者釆用组合或聚合来组合对象。 由于组合关系或聚合关系比继承关系耦合度低,满足“合成复用原则”,所以对象结构型模式比类结构型模式具有更大的灵活性。 结构型模式分为以下 7 种: 代理模式 适配器模式 装饰者模式 桥接模式 外观模式 组合模式