[LeetCode] Combination Sum III

216. Combination Sum III

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

  • Only numbers 1 through 9 are used.
  • Each number is used at most once.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> res;
vector<int> tmp;
dfs(k,n,res,tmp,1);
return res;
}

void dfs(int k, int n, vector<vector<int>>& res, vector<int>& tmp, int st) {
if(!k and !n) res.push_back(tmp);
if(!k or !n) return;
int cmp = 0;
for(int i = 9; i >= st and i > 9 - k; i--) cmp += i;
if(cmp < n) return;

for(int i = st; i <= 9 and i <= n; i++) {
tmp.push_back(i);
dfs(k-1, n-i, res, tmp, i+1);
tmp.pop_back();
}
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/02/07/PS/LeetCode/combination-sum-iii/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.