0.引言
● 216.组合总和III
● 17.电话号码的字母组合
216. 组合总和 III
| Category | Difficulty | Likes | Dislikes |
|---|---|---|---|
| algorithms | Medium (72.03%) | 644 | - |
找出所有相加之和为 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 <= 91 <= n <= 60
回溯
/*
* @lc app=leetcode.cn id=216 lang=cpp
*
* [216] 组合总和 III
*/
// @lc code=start
class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
std::vector<int> one_combine;
std::vector<std::vector<int>> res;
dfs(k, n, one_combine, res, 1);
return res;
}
private:
void dfs(int k, int n, std::vector<int>& one_combine,
std::vector<std::vector<int>>& res, int start_idx) {
// 1.结束条件
if (one_combine.size() == k &&
std::accumulate(one_combine.begin(), one_combine.end(), 0) == n) {
res.push_back(one_combine);
return;
} else if (one_combine.size() > k) {
return;
}
// 2.遍历本层
for (int i = start_idx; i <= 9; ++i) {
// 3.剪枝，剩余的已经不足以组成大小k的数组了
if (one_combine.size() + 9 - i + 1 < k) continue;
one_combine.push_back(i);
dfs(k, n, one_combine, res, i + 1);
one_combine.pop_back();
}
}
};
// @lc code=end
17.# 电话号码的字母组合
| Category | Difficulty | Likes | Dislikes |
|---|---|---|---|
| algorithms | Medium (58.05%) | 2384 | - |
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
image.png
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = ""
输出：[]
示例 3：
输入：digits = "2"
输出：["a","b","c"]
提示：
0 <= digits.length <= 4-
digits[i]是范围['2', '9']的一个数字。
回溯
/*
* @lc app=leetcode.cn id=17 lang=cpp
*
* [17] 电话号码的字母组合
*/
// @lc code=start
class Solution {
public:
vector<string> letterCombinations(string digits) {
if (digits == "") return {};
std::vector<std::string> str;
for (const auto& digit : digits) {
str.push_back(digit2str(digit));
}
std::string one_str;
std::vector<string> res;
dfs(str, 0, one_str, res);
return res;
}
private:
string digit2str(char digit) {
switch (digit) {
case '2': return "abc";
case '3': return "def";
case '4': return "ghi";
case '5': return "jkl";
case '6': return "mno";
case '7': return "pqrs";
case '8': return "tuv";
case '9': return "wxyz";
default: break;
}
return "";
}
void dfs(std::vector<std::string>& str, int row_idx /*从哪一层选*/,
std::string& one_str, std::vector<std::string>& res) {
// 1.终止条件
if (one_str.size() == str.size()) {
res.push_back(one_str);
return;
}
// 2.遍历该层的所有集合 col_idx选第几位
for (int col_idx = 0; col_idx < str[row_idx].size(); ++col_idx) {
// 3.剪枝：全遍历，没有剪枝
one_str += str[row_idx][col_idx];
dfs(str, row_idx + 1, one_str, res);
one_str.pop_back();
}
}
};
// @lc code=end
