题目描述：
找出所有相加之和为 $ n $ 的 $ k $ 个数的组合，且满足
- 只使用数字 $ 1 $ 到 $ 9 $
- 每个数字最多使用一次
返回所有可能的有效组合列表，不能包含相同的组合两次。
数据范围：
$ 2\le k \le 9, 1\le n \le 60 $
题解：
可以直接 dfs 深度为 $ k $ ，如果 step>k 直接返回，如果当前解的数量小于 $ k $ 也直接返回。注意使用 mask 打标记。
代码：
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
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
vector<vector<int>> ans;
void dfs(int mask, int step, int start, int k, int sum, int n, vector<int> &cur)
{
if(cur.size() > k) return;
if (sum == n && cur.size() == k)
{
ans.emplace_back(cur);
return;
}
if (step >= k)
{
return;
}
for (int i = start; i <= 9; ++i)
{
if (mask & (1 << i))
continue;
cur.emplace_back(i);
dfs(mask | (1 << i), step + 1, i + 1, k, sum + i, n, cur);
cur.pop_back();
}
}
vector<vector<int>> combinationSum3(int k, int n)
{
vector<int> cur;
int mask = 0;
dfs(mask, 0, 1, k, 0, n, cur);
return ans;
}
};
|