文章目录
- 77. 组合
- 216.组合总和III
- 17. 电话号码的字母组合
77. 组合
题目链接
文章讲解
class Solution {
public:vector<vector<int>> res; // 存储所有的组合vector<int> path; // 当前正在构建的组合// 回溯算法void solve(int n, int k, int start) {// 当 path 的大小达到 k，表示当前组合有效，加入结果集if (path.size() == k) {res.push_back(path); // 将当前组合添加到结果中return;}// 从 start 开始，尝试所有可能的数字for (int i = start; i <= n; i++) {path.push_back(i); // 选择当前数字solve(n, k, i + 1); // 继续选择下一个数字，注意这里递归是 i + 1，确保数字递增path.pop_back(); // 回溯，撤销选择，尝试其他可能的组合}}// 主函数，调用 solve 函数开始回溯vector<vector<int>> combine(int n, int k) {solve(n, k, 1); // 从 1 开始递归return res; // 返回所有组合结果}
};216.组合总和III
题目链接
文章讲解
class Solution {
public:vector<vector<int>> ans; // 存储所有符合条件的组合vector<int> path; // 当前正在构建的组合int sum = 0; // 当前组合的和// 回溯函数，递归地选择数字void solve(int k, int n, int start, int &sum) {// 1. 如果选择的数字个数达到了 k，检查和是否为 nif (path.size() == k) {if (sum == n) // 如果和恰好为 n，则加入结果ans.push_back(path);return;}// 2. 从 start 开始，尝试选择数字 1 到 9for (int i = start; i <= 9; i++) {path.push_back(i); // 选择当前数字sum += i; // 更新和solve(k, n, i + 1, sum); // 递归选择下一个数字sum -= i; // 回溯，撤销选择path.pop_back(); // 移除当前数字，继续尝试其他数字}}// 主函数，调用回溯函数开始求解vector<vector<int>> combinationSum3(int k, int n) {solve(k, n, 1, sum); // 从 1 开始递归，寻找所有组合return ans; // 返回所有组合结果}
};17. 电话号码的字母组合
题目链接
文章讲解
class Solution {
public:vector<string> ans; // 存储所有字母组合string path; // 当前递归路径，用于存储字母组合// 回溯函数，递归地生成字母组合void solve(vector<string>& s, int k, int start, const string& digits) {// 当 path 的长度达到 k（即字母组合的长度），将 path 加入到结果中if (path.size() == k) {ans.push_back(path); // 添加当前组合到结果return;}// 获取当前数字对应的字母组string p = s[digits[start] - '0'];// 遍历该字母组中的每个字母，递归生成组合for (int i = 0; i < p.size(); i++) {path += p[i]; // 选择当前字母solve(s, k, start + 1, digits); // 递归选择下一个数字path.pop_back(); // 回溯，撤销选择}}// 主函数，返回所有可能的字母组合vector<string> letterCombinations(string digits) {// 如果输入为空，直接返回空结果if (digits.empty()) return ans;// 初始化字母映射：数字 2-9 对应的字母集vector<string> s = {"", "", // 0 和 1 没有对应的字母"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};int k = digits.size(); // 目标组合的长度// 调用回溯函数，开始递归生成字母组合solve(s, k, 0, digits);return ans; // 返回所有字母组合}
};
)
)
