- 第 191 篇 -Date: 2026 - 03- 17| 周二Author: 郑龙浩仟墨今日算法or技巧回溯算法2026-03-17-算法刷题day25今日算法回溯算法本来今天是想把「回溯算法」的所有题都做完的但是我发现我低估了回溯算法题的难度了如果纯套模板的可能还能写出来但凡有变动或者某些特殊条件的我就会写不出来很难理解透彻总体看下来今天我可以说是什么也没学到上午满课然后下午开始搞回溯真的是把我头整大了太难理解了我放弃搞「回溯算法」了明天开始做一些「蓝桥杯」真题吧然后再刷一些基础算法题不能因为扣这种难以理解的题太长时间把那些基础的简单题给忘记了这就得不偿失了最终再落一个什么也没学到的结果不值得还有25天蓝桥杯希望接下来的25天我都能把握好每天的学习进度吧。文章目录2026-03-17-算法刷题day251-力扣17-电话号码的字母组合【题目】【思路】【代码】2-力扣39-组合总和【题目】【思路】【代码】3-力扣40-组合总和II【题目】【思路】【代码】1-力扣17-电话号码的字母组合【题目】给定一个仅包含数字2-9的字符串返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。示例 1输入digits 23输出[ad,ae,af,bd,be,bf,cd,ce,cf]示例 2输入digits 2输出[a,b,c]提示1 digits.length 4digits[i]是范围[2, 9]的一个数字。【思路】【代码】/* 2026-03-17-算法打卡day25 * 1-力扣17-电话号码的字母组合 * Author郑龙浩 * Date2026-03-16 * 算法/技巧回溯算法 递归 * 用时 */#includebits/stdc.husingnamespacestd;classSolution{public:vectorstringresults;// 存储所有字母组合结果的容器string path;// 当前正在构建的字母组合路径// 数字到字母的映射表// 索引0-9对应数字0-9其中数字2-9对应电话键盘上的字母string litters[10]{,// 数字0 - 无对应字母,// 数字1 - 无对应字母abc,// 数字2 - 对应字母abcdef,// 数字3 - 对应字母defghi,// 数字4 - 对应字母ghijkl,// 数字5 - 对应字母jklmno,// 数字6 - 对应字母mnopqrs,// 数字7 - 对应字母pqrs注意4个字母tuv,// 数字8 - 对应字母tuvwxyz// 数字9 - 对应字母wxyz注意4个字母};// 主函数返回所有可能的字母组合vectorstringletterCombinations(string digits){// 处理边界情况输入为空字符串if(digits.size()0)returnresults;// 从第0个数字开始回溯backtracking(digits,0);returnresults;}// 回溯函数// index: 当前处理到digits中的第几个数字从0开始// 也可以理解为递归树的当前深度voidbacktracking(stringdigits,intindex){// 终止条件已经处理完所有数字// 当index等于digits长度时说明已经为每个数字都选了一个字母if(indexdigits.size()){results.push_back(path);// 保存当前完整的字母组合return;// 结束当前递归分支}// 获取当前数字对应的字母串// digits[index]是字符如2减去0得到整数2// 用这个整数作为索引访问litters数组string slitters[digits[index]-0];// 遍历当前数字的所有可能字母for(charch:s){// 做出选择将当前字母加入路径path.push_back(ch);// 递归处理下一个数字// index1表示进入下一层递归处理digits中的下一个数字backtracking(digits,index1);// 回溯撤销选择回到当前状态// 为尝试当前数字的下一个字母做准备path.pop_back();}}};intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);return0;}2-力扣39-组合总和【题目】给你一个无重复元素的整数数组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 302 candidates[i] 40candidates的所有元素互不相同1 target 40【思路】【代码】/* 2026-03-17-算法打卡day25 * 2-力扣39-组合总和 * Author郑龙浩 * Date2026-03-16 * 算法/技巧回溯算法 递归 * 用时17 min * 说实话做的模模糊糊的主要是套模板 */#includebits/stdc.husingnamespacestd;classSolution{public:vectorvectorintresults;vectorintpath;vectorvectorintcombinationSum(vectorintcandidates,inttarget){backtracking(candidates,target,0);returnresults;}intsum(vectorintnums){intSum0;for(intit:nums)Sumit;returnSum;}voidbacktracking(vectorintcandidates,inttarget,intstartIndex){// 如果sum超过了target继续执行下去只会无限递归所以为了避免直接returnif(sum(path)target)return;// 刚开始没写这个if(sum(path)target){results.push_back(path);return;}for(intistartIndex;icandidates.size();i){path.push_back(candidates[i]);backtracking(candidates,target,i);// 因为可以重复当前数字所以下一次也从i开始path.pop_back();}return;}};intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);return0;}3-力扣40-组合总和II【题目】给定一个候选人编号的集合candidates和一个目标数target找出candidates中所有可以使数字和为target的组合。candidates中的每个数字在每个组合中只能使用一次。**注意**解集不能包含重复的组合。示例 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 1001 candidates[i] 501 target 30【思路】【代码】/* 2026-03-17-算法打卡day25 * 3-力扣40-组合总和II * Author郑龙浩 * Date2026-03-16 * 算法/技巧回溯算法 递归 * 用时1 小时 * 我依然没明白 * */#includebits/stdc.husingnamespacestd;classSolution{public:vectorvectorintresults;vectorintpath;vectorvectorintcombinationSum2(vectorintcandidates,inttarget){sort(candidates.begin(),candidates.end());// 如果要去重首先要给数组进行排序vectorboolused(candidates.size(),false);// 存储遇到过的元素backtracking(candidates,target,0,used);returnresults;}intSUM(vectorintnums){intsum0;for(intit:nums)sumit;returnsum;}voidbacktracking(vectorintcandidates,inttarget,intStartIndex,vectorboolused){intsumSUM(path);if(sumtarget)return;if(sumtarget){results.push_back(path);return;}/* 错误代码我第一次这么写的 错误原因没有去重(因为每个数字在每个组合中只能使用一次) 就是使用过的元素不能在重复选取了 “使用过”有两个维度1 同一树枝上使用过 2 同一树层上使用过 那么应该去重 同一树枝使用过还是同一树层使用过 应该要去重同一树层的“使用过”同一树枝上都是组合中的元素不需要去重 for (int i StartIndex; i candidates.size(); i) { path.push_back(candidates[i]); backtracking(candidates, target, i 1); path.pop_back(); } */for(intiStartIndex;icandidates.size();i){// 对于排序后相同的数字在同一层遍历中我们只选第一个跳过后面的相同数字避免重复组合if(i0candidates[i]candidates[i-1]used[i-1]false)continue;path.push_back(candidates[i]);used[i]true;backtracking(candidates,target,i1,used);used[i]false;// 回溯path.pop_back();}}};intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);return0;}
【算法打卡day25（2026-03-17 周二）今日算法：「回溯算法」】1-力扣17-电话号码的字母组合 2-力扣39-组合总和 3-力扣40-组合总和II
- 第 191 篇 -Date: 2026 - 03- 17| 周二Author: 郑龙浩仟墨今日算法or技巧回溯算法2026-03-17-算法刷题day25今日算法回溯算法本来今天是想把「回溯算法」的所有题都做完的但是我发现我低估了回溯算法题的难度了如果纯套模板的可能还能写出来但凡有变动或者某些特殊条件的我就会写不出来很难理解透彻总体看下来今天我可以说是什么也没学到上午满课然后下午开始搞回溯真的是把我头整大了太难理解了我放弃搞「回溯算法」了明天开始做一些「蓝桥杯」真题吧然后再刷一些基础算法题不能因为扣这种难以理解的题太长时间把那些基础的简单题给忘记了这就得不偿失了最终再落一个什么也没学到的结果不值得还有25天蓝桥杯希望接下来的25天我都能把握好每天的学习进度吧。文章目录2026-03-17-算法刷题day251-力扣17-电话号码的字母组合【题目】【思路】【代码】2-力扣39-组合总和【题目】【思路】【代码】3-力扣40-组合总和II【题目】【思路】【代码】1-力扣17-电话号码的字母组合【题目】给定一个仅包含数字2-9的字符串返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。示例 1输入digits 23输出[ad,ae,af,bd,be,bf,cd,ce,cf]示例 2输入digits 2输出[a,b,c]提示1 digits.length 4digits[i]是范围[2, 9]的一个数字。【思路】【代码】/* 2026-03-17-算法打卡day25 * 1-力扣17-电话号码的字母组合 * Author郑龙浩 * Date2026-03-16 * 算法/技巧回溯算法 递归 * 用时 */#includebits/stdc.husingnamespacestd;classSolution{public:vectorstringresults;// 存储所有字母组合结果的容器string path;// 当前正在构建的字母组合路径// 数字到字母的映射表// 索引0-9对应数字0-9其中数字2-9对应电话键盘上的字母string litters[10]{,// 数字0 - 无对应字母,// 数字1 - 无对应字母abc,// 数字2 - 对应字母abcdef,// 数字3 - 对应字母defghi,// 数字4 - 对应字母ghijkl,// 数字5 - 对应字母jklmno,// 数字6 - 对应字母mnopqrs,// 数字7 - 对应字母pqrs注意4个字母tuv,// 数字8 - 对应字母tuvwxyz// 数字9 - 对应字母wxyz注意4个字母};// 主函数返回所有可能的字母组合vectorstringletterCombinations(string digits){// 处理边界情况输入为空字符串if(digits.size()0)returnresults;// 从第0个数字开始回溯backtracking(digits,0);returnresults;}// 回溯函数// index: 当前处理到digits中的第几个数字从0开始// 也可以理解为递归树的当前深度voidbacktracking(stringdigits,intindex){// 终止条件已经处理完所有数字// 当index等于digits长度时说明已经为每个数字都选了一个字母if(indexdigits.size()){results.push_back(path);// 保存当前完整的字母组合return;// 结束当前递归分支}// 获取当前数字对应的字母串// digits[index]是字符如2减去0得到整数2// 用这个整数作为索引访问litters数组string slitters[digits[index]-0];// 遍历当前数字的所有可能字母for(charch:s){// 做出选择将当前字母加入路径path.push_back(ch);// 递归处理下一个数字// index1表示进入下一层递归处理digits中的下一个数字backtracking(digits,index1);// 回溯撤销选择回到当前状态// 为尝试当前数字的下一个字母做准备path.pop_back();}}};intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);return0;}2-力扣39-组合总和【题目】给你一个无重复元素的整数数组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 302 candidates[i] 40candidates的所有元素互不相同1 target 40【思路】【代码】/* 2026-03-17-算法打卡day25 * 2-力扣39-组合总和 * Author郑龙浩 * Date2026-03-16 * 算法/技巧回溯算法 递归 * 用时17 min * 说实话做的模模糊糊的主要是套模板 */#includebits/stdc.husingnamespacestd;classSolution{public:vectorvectorintresults;vectorintpath;vectorvectorintcombinationSum(vectorintcandidates,inttarget){backtracking(candidates,target,0);returnresults;}intsum(vectorintnums){intSum0;for(intit:nums)Sumit;returnSum;}voidbacktracking(vectorintcandidates,inttarget,intstartIndex){// 如果sum超过了target继续执行下去只会无限递归所以为了避免直接returnif(sum(path)target)return;// 刚开始没写这个if(sum(path)target){results.push_back(path);return;}for(intistartIndex;icandidates.size();i){path.push_back(candidates[i]);backtracking(candidates,target,i);// 因为可以重复当前数字所以下一次也从i开始path.pop_back();}return;}};intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);return0;}3-力扣40-组合总和II【题目】给定一个候选人编号的集合candidates和一个目标数target找出candidates中所有可以使数字和为target的组合。candidates中的每个数字在每个组合中只能使用一次。**注意**解集不能包含重复的组合。示例 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 1001 candidates[i] 501 target 30【思路】【代码】/* 2026-03-17-算法打卡day25 * 3-力扣40-组合总和II * Author郑龙浩 * Date2026-03-16 * 算法/技巧回溯算法 递归 * 用时1 小时 * 我依然没明白 * */#includebits/stdc.husingnamespacestd;classSolution{public:vectorvectorintresults;vectorintpath;vectorvectorintcombinationSum2(vectorintcandidates,inttarget){sort(candidates.begin(),candidates.end());// 如果要去重首先要给数组进行排序vectorboolused(candidates.size(),false);// 存储遇到过的元素backtracking(candidates,target,0,used);returnresults;}intSUM(vectorintnums){intsum0;for(intit:nums)sumit;returnsum;}voidbacktracking(vectorintcandidates,inttarget,intStartIndex,vectorboolused){intsumSUM(path);if(sumtarget)return;if(sumtarget){results.push_back(path);return;}/* 错误代码我第一次这么写的 错误原因没有去重(因为每个数字在每个组合中只能使用一次) 就是使用过的元素不能在重复选取了 “使用过”有两个维度1 同一树枝上使用过 2 同一树层上使用过 那么应该去重 同一树枝使用过还是同一树层使用过 应该要去重同一树层的“使用过”同一树枝上都是组合中的元素不需要去重 for (int i StartIndex; i candidates.size(); i) { path.push_back(candidates[i]); backtracking(candidates, target, i 1); path.pop_back(); } */for(intiStartIndex;icandidates.size();i){// 对于排序后相同的数字在同一层遍历中我们只选第一个跳过后面的相同数字避免重复组合if(i0candidates[i]candidates[i-1]used[i-1]false)continue;path.push_back(candidates[i]);used[i]true;backtracking(candidates,target,i1,used);used[i]false;// 回溯path.pop_back();}}};intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);return0;}
