LeetCode 0216.组合总和 III：回溯(剪枝) OR 二进制枚举

【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\times2^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这两种情况：

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

以上

时间复杂度 $O(\begin{pmatrix}C\\ k\end{pmatrix}\times k)$ ，其中 $C = 9$ ， $\begin{pmatrix}C\\ k\end{pmatrix}$ 为组合数从 $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