17.电话号码的字母组合力扣题目链接力扣题目链接class Solution { private: const string letterMap[10] { , // 0 , // 1 abc, // 2 def, // 3 ghi, // 4 jkl, // 5 mno, // 6 pqrs, // 7 tuv, // 8 wxyz, // 9 }; public: vectorstringres; string s; void backtracking(const string digits,int index){//为什么用 const string而不是 string digits值传递地址省内存 if(indexdigits.size()){ res.push_back(s); return; } int ddigits[index]-0; string letletterMap[d]; for(int i0;ilet.size();i){//可以思考一下这里是0还是index s.push_back(let[i]); backtracking(digits,index1); s.pop_back(); } } vectorstring letterCombinations(string digits) { s.clear(); res.clear(); backtracking(digits,0); return res; } };为什么用const string而不是string digits如果写成string digits按值传递每次递归调用都会复制整个字符串。如果digits很长比如 10 位递归深度 10就会产生 10 份拷贝浪费时间和空间。写成const string只传递一个“别名”地址所有递归层级共用同一份原始数据零拷贝。39. 组合总和力扣题目链接class Solution { public: vectorvectorintres; vectorintpath; int sum0; void backtracking(vectorint candidates, int target,int index){ if(sumtarget){ res.push_back(path); return; } else if(sumtarget){ return; } for(int iindex;icandidates.size();i){ sumcandidates[i]; path.push_back(candidates[i]); // if(sumtarget){ // sum-candidates[i]; // path.pop_back(); // return; // }为什莫 backtracking(candidates,target,i); sum-candidates[i]; path.pop_back(); } } vectorvectorint combinationSum(vectorint candidates, int target) { backtracking(candidates,target,0); return res; } };为什莫for循环里那个判断被//了for循环是“横向”的管兄弟递归调用是“纵向”的管子孙。8和8在下一层的时候就会在开头被忽略了然后回到第一层回溯。如果数组是乱序的如[8,7,4,3]你取了8发现超标比如8已经大于target11但后面的4和3并不超标甚至8311是正确答案所以在for循环里写return会直接杀死当前整个函数导致后面的4、3根本没机会被尝试。写在for循环里并用return杀死的是整个当前函数导致for循环后面的所有i都被跳过。写在函数顶部并用return杀死的只是当前这一层递归调用即当前这个分支for循环的父层依然坚挺可以继续尝试下一个i。40.组合总和II注意先给输入的数组排个序这样只会和前一个数字相同了。我在图中将used的变化用橘黄色标注上可以看出在candidates[i] candidates[i - 1]相同的情况下used[i - 1] true说明同一树枝candidates[i - 1]使用过used[i - 1] false说明同一树层candidates[i - 1]使用过可能有的录友想为什么 used[i - 1] false 就是同一树层呢因为同一树层used[i - 1] false 才能表示当前取的 candidates[i] 是从 candidates[i - 1] 回溯而来的。而 used[i - 1] true说明是进入下一层递归去下一个数所以是树枝上如图所示class Solution { public: vectorvectorintres; vectorintpath; int sum0; void backtracking(vectorint candidates, int target,int index, vectorbool used){ if(sumtarget){ res.push_back(path); return; } else if(sumtarget){ return; } for(int iindex;icandidates.size() sum candidates[i] target;i){ if (i 0 candidates[i] candidates[i - 1] used[i - 1] false) { continue; } sumcandidates[i]; path.push_back(candidates[i]); used[i]true; backtracking(candidates,target,i1,used); used[i]false; sum-candidates[i]; path.pop_back(); } } vectorvectorint combinationSum2(vectorint candidates, int target) { vectorbool used(candidates.size(), false); path.clear(); res.clear(); // 首先把给candidates排序让其相同的元素都挨在一起。 sort(candidates.begin(), candidates.end()); backtracking(candidates,target,0,used); return res; } };这里直接用startIndex来去重也是可以的 就不用used数组了。class Solution { private: vectorvectorint result; vectorint path; void backtracking(vectorint candidates, int target, int sum, int startIndex) { if (sum target) { result.push_back(path); return; } for (int i startIndex; i candidates.size() sum candidates[i] target; i) { // 要对同一树层使用过的元素进行跳过 if (i startIndex candidates[i] candidates[i - 1]) { continue; } sum candidates[i]; path.push_back(candidates[i]); backtracking(candidates, target, sum, i 1); // 和39.组合总和的区别1这里是i1每个数字在每个组合中只能使用一次 sum - candidates[i]; path.pop_back(); } } public: vectorvectorint combinationSum2(vectorint candidates, int target) { path.clear(); result.clear(); // 首先把给candidates排序让其相同的元素都挨在一起。 sort(candidates.begin(), candidates.end()); backtracking(candidates, target, 0, 0); return result; } };代码中的if条件是怎么做到“只杀横向不杀纵向”的看这句关键的判决条件cppif (i startIndex candidates[i] candidates[i - 1]) { continue; }我把这个条件拆成两个“关卡”关卡含义作用i startIndex当前尝试的这个元素不是这一层for循环的第一个元素即不是“新起点”。保护纵向如果是这一层的第一个元素i startIndex哪怕它和前一个数字相同比如递归深层里的第二个1也必须保留因为它代表了“在当前路径上使用这个重复数字”这个新方向。candidates[i] candidates[i - 1]当前元素和它前一个元素的值相等。执行横向跳过既然前一个相同值已经作为“起点”试过了所有后续可能当前这个直接跳过避免重复。3. 用具体例子验证candidates [1, 1, 2],target 3为了直观我们只看根节点第一层和它下面的第二层根节点第一层startIndex0i0第一个1i startIndex是0 0不成立保留。进入递归找到了[1,1,2]和[1,2]。i1第二个1i startIndex是1 0成立且candidates[1] candidates[0]11成立。执行continue跳过。如果这里不跳过以第二个1开头会找到[1,2]这和刚才以第一个1找到的[1,2]完全重复进入第一个1的递归内部第二层startIndex1在这一层里for循环从i1开始。i1第二个1此时i startIndex是1 1不成立所以即使candidates[1] candidates[0]11也不会被跳过。结果第二个1被成功加入路径形成了[1, 1]为后续找到[1,1,2]这个正确答案保留了机会。
