代码随想录
别看本篇选的是组合总和III，而不是组合总和，本题和上一篇77.组合相比难度刚刚好！
216.组合总和III
找出所有相加之和为 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]]
算法公开课
《代码随想录》算法视频公开课 (opens new window)：和组合问题有啥区别？回溯算法如何剪枝？| LeetCode：216.组合总和III (opens new window)，相信结合视频再看本篇题解，更有助于大家对本题的理解。
思路
本题就是在[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的组合。
选取过程如图：
图中，可以看出，只有最后取到集合（1，3）和为4 符合条件。
回溯三部曲
和77. 组合 (opens new window)一样，依然需要一维数组path来存放符合条件的结果，二维数组result来存放结果集。
这里我依然定义path 和 result为全局变量。
至于为什么取名为path？从上面树形结构中，可以看出，结果其实就是一条根节点到叶子节点的路径。
vector<vector<int>> result;
vector<int> path;
1 2
接下来还需要如下参数：
- 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)
1 2 3
其实这里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;
}
1 2 3 4
本题和77. 组合 (opens new window)区别之一就是集合固定的就是9个数[1,...,9]，所以for循环固定i<=9
如图：
处理过程就是 path收集每次选取的元素，相当于树型结构里的边，sum来统计path里元素的总和。
代码如下：
for (int i = startIndex; i <= 9; i++) {
sum += i;
path.push_back(i);
backtracking(targetSum, k, sum, i + 1);
sum -= i;
path.pop_back();
}
1 2 3 4 5 6 7
别忘了处理过程 和 回溯过程是一一对应的，处理有加，回溯就要有减！
参照关于回溯算法，你该了解这些！ (opens new window)中的模板，不难写出如下C++代码：
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(int targetSum, int k, int sum, int startIndex) {
if (path.size() == k) {
if (sum == targetSum) result.push_back(path);
return;
}
for (int i = startIndex; i <= 9; i++) {
sum += i;
path.push_back(i);
backtracking(targetSum, k, sum, i + 1);
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;
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
剪枝
这道题目，剪枝操作其实是很容易想到了，想必大家看上面的树形图的时候已经想到了。
如图：
已选元素总和如果已经大于n（图中数值为4）了，那么往后遍历就没有意义了，直接剪掉。
那么剪枝的地方可以放在递归函数开始的地方，剪枝代码如下：
if (sum > targetSum) {
return;
}
1 2 3
当然这个剪枝也可以放在 调用递归之前，即放在这里，只不过要记得 要回溯操作给做了。
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);
sum -= i;
path.pop_back();
}
1 2 3 4 5 6 7 8 9 10 11 12
和回溯算法：组合问题再剪剪枝 (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;
}
for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
sum += i;
path.push_back(i);
backtracking(targetSum, k, sum, i + 1);
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;
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
- 时间复杂度: O(n * 2^n)
- 空间复杂度: O(n)
总结
开篇就介绍了本题与77.组合 (opens new window)的区别，相对来说加了元素总和的限制，如果做完77.组合 (opens new window)再做本题在合适不过。
分析完区别，依然把问题抽象为树形结构，按照回溯三部曲进行讲解，最后给出剪枝的优化。
相信做完本题，大家对组合问题应该有初步了解了。
其他语言版本
Java
模板方法
class Solution {
List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
backTracking(n, k, 1, 0);
return result;
}
private void backTracking(int targetSum, int k, int startIndex, int sum) {
if (sum > targetSum) {
return;
}
if (path.size() == k) {
if (sum == targetSum) result.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
path.add(i);
sum += i;
backTracking(targetSum, k, i + 1, sum);
path.removeLast();
sum -= i;
}
}
}
class Solution {
LinkedList<Integer> path = new LinkedList<>();
List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
build(k, n, 1, 0);
return ans;
}
private void build(int k, int n, int startIndex, int sum) {
if (sum > n) return;
if (path.size() > k) return;
if (sum == n && path.size() == k) {
ans.add(new ArrayList<>(path));
return;
}
for(int i = startIndex; i <= 9; i++) {
path.add(i);
sum += i;
build(k, n, i + 1, sum);
sum -= i;
path.removeLast();
}
}
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
其他方法
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> list = new ArrayList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
res.clear();
list.clear();
backtracking(k, n, 9);
return res;
}
private void backtracking(int k, int n, int maxNum) {
if (k == 0 && n == 0) {
res.add(new ArrayList<>(list));
return;
}
if (maxNum == 0
|| n > k * maxNum - k * (k - 1) / 2
|| n < (1 + k) * k / 2) {
return;
}
list.add(maxNum);
backtracking(k - 1, n - maxNum, maxNum - 1);
list.remove(list.size() - 1);
backtracking(k, n, maxNum - 1);
}
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
Python
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
result = []
self.backtracking(n, k, 0, 1, [], result)
return result
def backtracking(self, targetSum, k, currentSum, startIndex, path, result):
if currentSum > targetSum:
return
if len(path) == k:
if currentSum == targetSum:
result.append(path[:])
return
for i in range(startIndex, 9 - (k - len(path)) + 2):
currentSum += i
path.append(i)
self.backtracking(targetSum, k, currentSum, i + 1, path, result)
currentSum -= i
path.pop()
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Go
回溯+减枝
var (
res [][]int
path []int
)
func combinationSum3(k int, n int) [][]int {
res, path = make([][]int, 0), make([]int, 0, k)
dfs(k, n, 1, 0)
return res
}
func dfs(k, n int, start int, sum int) {
if len(path) == k {
if sum == n {
tmp := make([]int, k)
copy(tmp, path)
res = append(res, tmp)
}
return
}
for i := start; i <= 9; i++ {
if sum + i > n || 9-i+1 < k-len(path) {
break
}
path = append(path, i)
dfs(k, n, i+1, sum+i)
path = path[:len(path)-1]
}
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
JavaScript
var combinationSum3 = function (k, n) {
let result = [],
path = [];
const backtracking = (_k, targetSum, sum, startIndex) => {
if (path.length === _k) {
if (sum === targetSum) {
result.push(path.slice());
}
return;
}
for (let i = startIndex; i <= 9; i++) {
path.push(i);
sum += i;
backtracking(_k, targetSum, sum, i + 1);
sum -= i;
path.pop();
}
};
backtracking(k, n, 0, 1);
return result;
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
var combinationSum3 = function (k, n) {
let result = [],
path = [];
const backtracking = (_k, targetSum, sum, startIndex) => {
if (sum > targetSum) {
return;
}
if (path.length === _k) {
if (sum === targetSum) {
result.push(path.slice());
}
return;
}
for (let i = startIndex; i <= 9 - (_k - path.length) + 1; i++) {
path.push(i);
sum += i;
backtracking(_k, targetSum, sum, i + 1);
sum -= i;
path.pop();
}
};
backtracking(k, n, 0, 1);
return result;
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
TypeScript
function combinationSum3(k: number, n: number): number[][] {
const resArr: number[][] = [];
function backTracking(k: number, n: number, sum: number, startIndex: number, tempArr: number[]): void {
if (sum > n) return;
if (tempArr.length === k) {
if (sum === n) {
resArr.push(tempArr.slice());
}
return;
}
for (let i = startIndex; i <= 9 - (k - tempArr.length) + 1; i++) {
tempArr.push(i);
backTracking(k, n, sum + i, i + 1, tempArr);
tempArr.pop();
}
}
backTracking(k, n, 0, 1, []);
return resArr;
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Rust
impl Solution {
pub fn combination_sum3(k: i32, n: i32) -> Vec<Vec<i32>> {
let mut result = vec![];
let mut path = vec![];
Self::backtrace(&mut result, &mut path, n, k, 0, 1);
result
}
pub fn backtrace(
result: &mut Vec<Vec<i32>>,
path: &mut Vec<i32>,
target_sum: i32,
k: i32,
sum: i32,
start_index: i32,
) {
if sum > target_sum {
return;
}
let len = path.len() as i32;
if len == k {
if sum == target_sum {
result.push(path.to_vec());
}
return;
}
for i in start_index..=9 - (k - len) + 1 {
path.push(i);
Self::backtrace(result, path, target_sum, k, sum + i, i + 1);
path.pop();
}
}
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
C
int* path;
int pathTop;
int** ans;
int ansTop;
int getPathSum() {
int i;
int sum = 0;
for(i = 0; i < pathTop; i++) {
sum += path[i];
}
return sum;
}
void backtracking(int targetSum, int k, int sum, int startIndex) {
if(pathTop == k) {
if(sum == targetSum) {
int* tempPath = (int*)malloc(sizeof(int) * k);
int j;
for(j = 0; j < k; j++)
tempPath[j] = path[j];
ans[ansTop++] = tempPath;
}
return;
}
int i;
for (i = startIndex; i <= 9; i++) {
sum += i;
path[pathTop++] = i;
backtracking(targetSum, k, sum, i + 1);
sum -= i;
pathTop--;;
}
}
int** combinationSum3(int k, int n, int* returnSize, int** returnColumnSizes){
path = (int*)malloc(sizeof(int) * k);
ans = (int**)malloc(sizeof(int*) * 20);
pathTop = ansTop = 0;
backtracking(n, k, 0, 1);
*returnSize = ansTop;
*returnColumnSizes = (int*)malloc(sizeof(int) * ansTop);
int i;
for(i = 0; i < ansTop; i++) {
(*returnColumnSizes)[i] = k;
}
return ans;
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
Swift
func combinationSum3(_ count: Int, _ targetSum: Int) -> [[Int]] {
var result = [[Int]]()
var path = [Int]()
func backtracking(sum: Int, start: Int) {
if sum > targetSum { return }
if path.count == count {
if sum == targetSum {
result.append(path)
}
return
}
let end = 9
guard start <= end else { return }
for i in start ... end {
path.append(i)
backtracking(sum: sum + i, start: i + 1)
path.removeLast()
}
}
backtracking(sum: 0, start: 1)
return result
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
Scala
object Solution {
import scala.collection.mutable
def combinationSum3(k: Int, n: Int): List[List[Int]] = {
var result = mutable.ListBuffer[List[Int]]()
var path = mutable.ListBuffer[Int]()
def backtracking(k: Int, n: Int, sum: Int, startIndex: Int): Unit = {
if (sum > n) return
if (sum == n && path.size == k) {
result.append(path.toList)
return
}
for (i <- startIndex to (9 - (k - path.size) + 1)) {
path.append(i)
backtracking(k, n, sum + i, i + 1)
path = path.take(path.size - 1)
}
}
backtracking(k, n, 0, 1)
result.toList
}
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
C#
public class Solution
{
public IList<IList<int>> res = new List<IList<int>>();
public IList<int> path = new List<int>();
public IList<IList<int>> CombinationSum3(int k, int n)
{
BackTracking(k, n, 0, 1);
return res;
}
public void BackTracking(int k, int n, int sum, int start)
{
if (path.Count == k)
{
if (sum == n)
res.Add(new List<int>(path));
return;
}
for (int i = start; i <= 9; i++)
{
sum += i;
path.Add(i);
BackTracking(k, n, sum, i + 1);
sum -= i;
path.RemoveAt(path.Count - 1);
}
}
}
public class Solution
{
public IList<IList<int>> res = new List<IList<int>>();
public IList<int> path = new List<int>();
public IList<IList<int>> CombinationSum3(int k, int n)
{
BackTracking(k, n, 0, 1);
return res;
}
public void BackTracking(int k, int n, int sum, int start)
{
if (sum > n)
return;
if (path.Count == k)
{
if (sum == n)
res.Add(new List<int>(path));
return;
}
for (int i = start; i <= 9 - (k - path.Count) + 1; i++)
{
sum += i;
path.Add(i);
BackTracking(k, n, sum, i + 1);
sum -= i;
path.RemoveAt(path.Count - 1);
}
}
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
上次更新：: 3/18/2025, 4:44:09 PM
Was this article displayed correctly? Not happy with what you see?
If you often open multiple tabs and struggle to keep track of them, Tabs Reminder is the solution you need. Tabs Reminder lets you set reminders for tabs so you can close them and get notified about them later. Never lose track of important tabs again with Tabs Reminder!
Try our Chrome extension today!
Share this article with your
friends and colleagues.
Earn points from views and
referrals who sign up.
Learn more
Save articles to reading lists
and access them on any device