Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit29a3dca

Browse files
Update
1 parenta5f6650 commit29a3dca

File tree

3 files changed

+36
-8
lines changed

3 files changed

+36
-8
lines changed

‎README.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -477,7 +477,7 @@ backtracking() {
477477

478478
大家好，我是程序员Carl，ACM 校赛、黑龙江省赛、东北四省赛金牌，和亚洲区域赛铜牌获得者，哈工大计算机硕士毕业，先后在腾讯和百度从事后端技术研发，CSDN博客专家。对算法和C++后端技术有一定的见解，利用工作之余重新刷leetcode。
479479

480-
**加我的微信，备注：组队刷题**， 拉你进刷题群，每天一道经典题目分析，而且题目不是孤立的，每一道题目之间都是有关系的，都是由浅入深一脉相承的，所以学习效果最好是每篇连续着看，也许之前你会某些知识点，但是一直没有把知识点串起来，这里每天一篇文章就会帮你把知识点串起来。我也花了不少精力来整理我的题解，**而且我不会在群里发任何广告，纯自己学习和分享。 欢迎你的加入！**
480+
**加我的微信，备注：「个人简单介绍」+「组队刷题」**， 拉你进刷题群，每天一道经典题目分析，而且题目不是孤立的，每一道题目之间都是有关系的，都是由浅入深一脉相承的，所以学习效果最好是每篇连续着看，也许之前你会某些知识点，但是一直没有把知识点串起来，这里每天一篇文章就会帮你把知识点串起来。我也花了不少精力来整理我的题解，**而且我不会在群里发任何广告，纯自己学习和分享。 欢迎你的加入！**
481481

482482
<aname="微信"></a>
483483
<imgsrc="https://img-blog.csdnimg.cn/20200712232919673.jpeg"data-img="1"width="175"height="175">

‎pics/216.组合总和III.png‎

86.6 KB
Loading

‎problems/0216.组合总和III.md‎

Lines changed: 35 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -18,37 +18,65 @@
1818

1919
#思路
2020

21+
这道题目注意一下几点：
22+
23+
* 解集不能包含重复的组合。 说明不用去重了，难度就小一些。
24+
* 求的是组合，那么集合没有顺序，for里面依然要从startIndex开始（如果是排列的话，就从0开始）
25+
26+
本题k相当于限制了树的深度，9就是树的宽度。
27+
28+
选取过程如图：
29+
30+
<imgsrc='../pics/216.组合总和III.png'width=600> </img></div>
31+
32+
那么这还是一道标准的模板题，模板：
33+
34+
```
35+
backtracking() {
36+
if (终止条件) {
37+
存放结果;
38+
}
39+
40+
for (选择：选择列表（可以想成树中节点孩子的数量）) {
41+
递归，处理节点;
42+
backtracking();
43+
回溯，撤销处理结果
44+
}
45+
}
46+
```
47+
48+
2149

2250
#C++代码
2351

2452
```
2553
class Solution {
2654
private:
2755
vector<vector<int>> result;
28-
void backtracking(int target, int k, vector<int>& vec, int num, int sum, int startIndex) {
56+
vector<int> path;
57+
void backtracking(int target, int k, int num, int sum, int startIndex) {
2958
if (sum > target || num > k) {
3059
return;
3160
}
3261
if (num == k && sum == target) {
33-
result.push_back(vec);
62+
result.push_back(path);
3463
return;
3564
}
3665
3766
for (int i = startIndex; i <= 9; i++) {
3867
sum += i;
39-
vec.push_back(i);
68+
path.push_back(i);
4069
num++;
41-
backtracking(target, k,vec,num, sum, i + 1);
70+
backtracking(target, k, num, sum, i + 1);
4271
num--;
4372
sum -= i;
44-
vec.pop_back();
73+
path.pop_back();
4574
}
4675
}
4776
4877
public:
4978
vector<vector<int>> combinationSum3(int k, int n) {
50-
vector<int> vec;
51-
backtracking(n, k, vec, 0, 0, 1);
79+
backtracking(n, k, 0, 0, 1);
5280
return result;
5381
5482
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp