Day21 | Part2
约 81 个字 62 行代码 预计阅读时间 1 分钟
相比77.组合,加了元素总和的限制。选取过程示意图
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | vector<vector<int>> res;
vector<int> path;
void backtracking(int k, int n, int idx, int sum) {
if (sum > n) return; // 剪枝
if(path.size() == k) {
if(sum == n) res.push_back(path);
return;
}
for(int i = idx; i <= 9; i ++) {
sum += i;
path.push_back(i);
backtracking(k, n, i + 1, sum);
sun -= i; // 回溯
path.pop_back(i);
}
}
vector<vector<int>> combinationSum3(int k, int n) {
backtracking(k, n, 1, 0);
return res;
}
|
当然, sum参数可以不要, 而是通过n减去每次值看最终是否为0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | vector<vector<int>> res;
vector<int> path;
void backtracking(int k, int n, int idx) {
if(n < 0 || path.size() > k) return;
if(n == 0 && path.size() == k) {
res.push_back(path);
return;
}
for(int i = idx; i <= 9; i ++) {
path.push_back(i);
backtracking(k, n - i, i + 1);
path.pop_back();
}
}
vector<vector<int>> combinationSum3(int k, int n) {
backtracking(k, n, 1);
return res;
}
|
要有数字到字符串的映射关系, 用数组或vector → 示意图
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | vector<string> digit_map = {
"", "", "abc", "def", "ghi",
"jkl","mno", "pqrs", "tuv", "wxyz",
};
void backtracking(string digits,vector<string>& res, int idx, string &s) {
if(digits.size() == 0) return;
if(idx == digits.size()) {
res.push_back(s);
return;
}
int d = digits[idx] - '0'; // idx指向的数字转为int
string d_to_s = digit_map[d]; // 数字对应的字符串
for(int i = 0; i < d_to_s.size(); i ++) {
s.push_back(d_to_s[i]);
backtracking(digits, res, idx + 1, s);
s.pop_back(); // 回溯
}
}
vector<string> letterCombinations(string digits) {
vector<string> res;
string s;
backtracking(digits, res, 0, s);
return res;
}
|
