当前位置：首页 > ds >正文

算法打卡22天

ds 2025/7/2 14:39:20

电话号码的字母组合

（力扣 17题）
定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
示例 2：

输入：digits = “”
输出：[]
示例 3：

输入：digits = “2”
输出：[“a”,“b”,“c”]

代码

class Solution
{
public:// 存放结果集vector<vector<int>> result;//  符合条件的结果vector<int> path;// targetSum：目标和，也就是题目中的n。// k：题目中要求k个数的集合。// sum：已经收集的元素的总和，也就是path里元素的总和。// startIndex：下一层for循环搜索的起始位置。void backtracking(int targetSum, int k, int sum, int startIndex){// 剪枝操作if(sum > targetSum){return;}// 回溯结束条件if (path.size() == k) // 取到要求的数字{if (targetSum == sum){result.push_back(path);}// sum != targetSum 直接返回return;}// 单层搜索过程（剪枝）for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++){sum += i;path.push_back(i);backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndexsum -= i;                               // 回溯path.pop_back();}}vector<vector<int>> combinationSum3(int k, int n){path.clear();result.clear();backtracking(n, k ,0 , 1);return result;}
};

给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。

candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：

输入: candidates = [2], target = 1
输出: []

提示：

1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates 的所有元素互不相同
1 <= target <= 40

代码

class Solution
{
public:vector<vector<int>> result;vector<int> path;void backtracking(const vector<int> &candidates, int target, int sum, int startIndex){// 递归终止条件(叶子节点)// if (sum > target)//     return;      //剪枝之后就不需要了if (sum == target){result.push_back(path);return;}// 单层搜索的逻辑for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++)   //总集合排序之后// 如果下一层的sum（就是本层的 sum + candidates[i]）已经大于target，就可以结束本轮for循环的遍历。{sum += candidates[i];path.push_back(candidates[i]);backtracking(candidates, target, sum, i);//   回溯sum -=  candidates[i];path.pop_back();}}vector<vector<int>> combinationSum(vector<int> &candidates, int target){result.clear();path.clear();if(candidates.size() ==  0)return result;// 需要排序,剪枝sort(candidates.begin(), candidates.end());backtracking(candidates, target, 0, 0);return result;}
};

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

注意：解集不能包含重复的组合。

组合总和

（力扣39 题）

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

提示:

1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

代码

class Solution
{public:vector<vector<int>> combinationSum2(vector<int> &candidates, int target){vector<bool> used(candidates.size(), false);// 初始化result.clear();path.clear();// 首先把给candidates排序，让其相同的元素都挨在一起。sort(candidates.begin(), candidates.end());backtracking(candidates, target, 0, 0, used);return result;}private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int> &candidates, int target, int sum, int startIndex, vector<bool> &used){if (target == sum){result.push_back(path);return;}for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++){// used[i - 1] == true，说明同一树枝candidates[i - 1]使用过// used[i - 1] == false，说明同一树层candidates[i - 1]使用过// 要对同一树层使用过的元素进行跳过if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false)continue;sum += candidates[i];path.push_back(candidates[i]);used[i] = true;// 递归backtracking(candidates, target, sum, i + 1, used);used[i] = false;sum -= candidates[i];path.pop_back();}}
};