leetcode216--组合总和III

devtools/2025/1/16 1:35:21/

1. 题意

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

  • 只使用数字1到9
  • 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。

2. 题解

2.1 回溯
class Solution {
public:void search(int begin, vector<vector<int>> &ans,vector<int> &seq, int sum, int n,int k) {if ( sum == n && seq.size() == k) {ans.emplace_back( seq );return;}if ( sum > n || seq.size() > k)return;for (int i = begin; i < 10; i++) {seq.emplace_back(i);search( i + 1,ans, seq, sum + i, n, k);seq.pop_back();}}vector<vector<int>> combinationSum3(int k, int n) {int mx = (9 + (10 - k)) * k / 2;vector<vector<int>> ans;if ( mx < n)return ans;vector<int> seq;search(1, ans, seq, 0, n, k);return ans;}
};
2.2 二进制枚举

直接枚举每一种可能,判断是否满足即可。

class Solution {
public:bool check(int v, int n, int k) {int one_cnt  = 0;int sum = 0;for (int i = 0;i < 9; ++i) {if (v & (1 << i))one_cnt++, sum += i + 1;}return one_cnt == k && sum == n;}vector<vector<int>> combinationSum3(int k, int n) {vector<vector<int>> ans;vector<int> seq;for (int i = 1; i < (1 << 9); ++i) {if ( check(i, n, k) ) {seq.clear();for (int j = 0;j < 9; ++j) {if ( i & (1 << j))seq.emplace_back( j + 1);}ans.emplace_back(seq);}}return ans;}
};

http://www.ppmy.cn/devtools/18037.html

相关文章

1.C++入门(上)

目录 1.C关键字 2.命名空间 作用域方面的优化 a.命名空间定义 b.命名空间使用 3.C 输入&输出 1.C关键字 C有63个关键字&#xff0c;C语言有32个关键字&#xff0c;存在重叠如荧光笔标出 2.命名空间 作用域方面的优化 如果变量&#xff0c;函数和类的名称都存在于全…

Frida入门笔记

Frida入门笔记 1.背景1.1 概述1.2 主要功能1.3 应用场景1.4 使用方法 1.背景 Frida 是一款强大的动态代码插桩工具&#xff0c;它允许开发者在运行时对目标应用程序进行实时操作和分析。以下是对 Frida 的详细介绍&#xff1a; 1.1 概述 Frida 是一个跨平台的动态代码插桩框…

(ChatGPT中文、吾爱Al、核桃、WeexAl地址发布页、ai创作、Chat中文)分享好用的ChatGPT

目录 1、ChatGPT 中文 - Chat GPT 2、吾爱AI 3、 核桃 4、WeexAI 地址发布页 5、ai创作

js将后端返回的blob请求下载

首先在请求里加上responseType: blob http({url: ,method: post,headers: {Content-Type: application/json},responseType: blob,data: saveObj })然后再返参里下载 http({url: ,method: post,headers: {Content-Type: application/json},responseType: blob,data: saveObj}…

C语言数据类型的介绍,类型的基本归类,整型在内存中的存储,原码、反码、补码,大小端等介绍

文章目录 前言一、数据类型的介绍类型的意义 1. 类型的基本归类&#xff08;1&#xff09;. 整型家族&#xff08;2&#xff09;. 浮点数家族&#xff08;3&#xff09;. 构造类型&#xff08;4&#xff09;. 指针类型&#xff08;5&#xff09;. 空类型 二、整型在内存中的存储…

深度学习基础之《TensorFlow框架(12)—图片数据》

一、图像基本知识 1、如何转换图片文件 回忆&#xff1a;之前我们在特征抽取中讲过如何将文本处理成数据 思考&#xff1a;如何将图片文件转换成机器学习算法能够处理的数据&#xff1f; 我们经常接触到的图片有两种&#xff0c;一种是黑白图片&#xff08;灰度图&#xff09;…

设计模式:合成复用原则(Composite Reuse Principle,CRP)介绍

合成复用原则&#xff08;Composite Reuse Principle&#xff0c;CRP&#xff09;是面向对象设计原则之一&#xff0c;它强调通过组合已有的对象来实现新的功能&#xff0c;而不是通过继承已有的类来实现。合成复用原则的核心思想是尽量使用对象组合而不是类继承&#xff0c;从…

阿里云mysql8.0 this is incompatible withsql mode=only full group by

阿里云RDS中mysql5.6升级为8.0后&#xff0c;出现如下问题&#xff1a; ### Error querying database. Cause:java.sql.SQLSyntaxErrorException: Expression #1 of SELECT listis not in GROUP BY clause and contains nonaggregatedcolumn temp.product_id which is not fun…