【LetMeFly】216.组合总和 III：回溯(剪枝) OR 二进制枚举

力扣题目链接：https://leetcode.cn/problems/combination-sum-iii/

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

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

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

 

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

示例 3:

输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。

 

提示:

• 2 <= k <= 9
• 1 <= n <= 60

方法一：二进制枚举（选与不选）

一共$9$个数，每个数选与不选一共有$2^9=512$种情况。

我们只需要使用一个二进制数一一枚举这$512$种情况即可。

二进制数的每一位代表每个数的选与不选，对于某种情况，只需要判断是否恰好为$k$个数，以及是否恰好和为$n$即可。

• 时间复杂度$O(C\times 2^C)$，其中$C=9$
• 空间复杂度$O(C)$

AC代码

C++

class Solution {
public:vector<vector<int>> combinationSum3(int k, int n) {vector<vector<int>> ans;int to = 1 << 9;for (int i = 0; i < to; i++) {if (__builtin_popcount(i) != k) {continue;}vector<int> thisSolution;int thisCnt = 0;for (int j = 0; j < 9; j++) {if (i & (1 << j)) {thisCnt += j + 1;thisSolution.push_back(j + 1);}}if (thisCnt == n) {ans.push_back(thisSolution);}}return ans;}
};

Python

# from typing import Listclass Solution:def combinationSum3(self, k: int, n: int) -> List[List[int]]:ans = []for i in range(1 << 9):if i.bit_count() != k:  # Python 3.9.4中似乎无此函数continuethisSolution = []thisCnt = 0for j in range(9):if i & (1 << j):thisCnt += j + 1thisSolution.append(j + 1)if thisCnt == n:ans.append(thisSolution)return ans

方法二：回溯+剪枝(DFS)

写一个函数dfs(k, n, index)来求所有“从[index,9]范围内选k个数使得和为n”的情况。

• 如果k = 0 && n == 0，则说明当前方案为一个可行方案，计入答案中且返回
• 如果index > n || index == 10 || k <= 0，则终止（剪枝/递归终止条件）

这样，就只有选与不选index这两种情况：

1. 不选index：直接递归调用dfs(k, n, index + 1)
2. 选index：将index加入当前选择方案的数组中、递归调用dfs(k - 1, n - index, index + 1)、将index从当前方案中移除（回溯）

以上

• 时间复杂度$O(\left(\begin{array}{c}C\\ k\end{array}\right)\times k)$，其中$C=9$，$\left(\begin{array}{c}C\\ k\end{array}\right)$为组合数从$C$个数里面选$k$个
• 空间复杂度$O(C)$

AC代码

C++

class Solution {
private:vector<vector<int>> ans;vector<int> now;// 从[index,9]范围内选k个数使得和为nvoid dfs(int k, int n, int index) {if (!k && !n) {ans.push_back(now);return;}if (index > n || index == 10 || k <= 0) {return;}// not choosedfs(k, n, index + 1);// choosenow.push_back(index);dfs(k - 1, n - index, index + 1);now.pop_back();}
public:vector<vector<int>> combinationSum3(int k, int n) {dfs(k, n, 1);return ans;}
};

小数据情况下，方法一的实际执行效果也许会优于方法二。

Python

# from typing import Listclass Solution:def dfs(self, k: int, n: int, index: int) -> None:if not k and not n:self.ans.append(self.now[:])returnif index > n or index == 10 or k <= 0:returnself.dfs(k, n, index + 1)self.now.append(index)self.dfs(k - 1, n - index, index + 1)self.now.pop()def combinationSum3(self, k: int, n: int) -> List[List[int]]:self.ans = []self.now = []self.dfs(k, n, 1)return self.ans

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/138033273