👉组合总和 III👈
其实组合总和 III 的解题思路也和组合的思路是一样的。也是套用回溯算法的模板，就是修改一下递归终止的条件和 for 循环横向遍历是做到操作。
class Solution { private: vector<vector<int>> result; vector<int> path; // tagetSum为目标和 // k为要求每个组合中数字的个数 // startIndex为下一层递归开始遍历的下标 // sum为路径和 void backtracking(int targetSum, int k, int startIndex, int sum) { if(path.size() == k) { if(sum == targetSum) { result.push_back(path); // 收集结果 } return; } // 横向遍历 for(int i = startIndex; i <= 9; ++i) { // 处理节点 sum += i; path.push_back(i); // 递归,纵向遍历 backtracking(targetSum, k, i + 1, sum); // 回溯 sum -= i; path.pop_back(); } } public: vector<vector<int>> combinationSum3(int k, int n) { result.clear(); // 可以不做 path.clear(); // 可以不做 backtracking(n, k, 1, 0); return result; } };
注：startIndex 是为了防止重复选数的。
组合总和 III 的剪枝优化有两个地方可以优化，第一个是和组合的剪枝优化一下，就是已经选的元素个数加上剩余的元素个数无法到达 k；还有一个优化就是，如果 sum 已经大于 targetSum 了，就没必要再往下搜索了（尽管所需要元素个数没有达到 k 个）。这个优化当做递归的终止条件，也可以放在 for 横向遍历中。下方的代码是放在 for 的横向遍历中，注意剪枝之前需要把回溯做了。
class Solution { private: vector<vector<int>> result; vector<int> path; // tagetSum为目标和 // k为要求每个组合中数字的个数 // startIndex为下一层递归开始遍历的下标 // sum为路径和 void backtracking(int targetSum, int k, int startIndex, int sum) { if(path.size() == k) { if(sum == targetSum) { result.push_back(path); } return; } // 剪枝优化 for(int i = startIndex; i <= 9 + 1 - (k - path.size()); ++i) { sum += i; path.push_back(i); if(sum > targetSum) // 剪枝优化 { sum -= i; // 剪枝之前先把回溯做了 path.pop_back(); // 剪枝之前先把回溯做了 return; } backtracking(targetSum, k, i + 1, sum); sum -= i; path.pop_back(); } } public: vector<vector<int>> combinationSum3(int k, int n) { backtracking(n, k, 1, 0); return result; } };
👉组合总和👈
给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
组合总和这道题目是给定了候选数字的数组和目标和。那么 for 循环遍历的集合就变成了候选数字数组。因为可以选取重复的元素，那么下一层递归还是从 i 开始搜索。注：因为给出的数字集合有序的，所以可以先将其排序。
class Solution { private: vector<vector<int>> result; vector<int> path; void backtracking(const vector<int>& 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) { // 各种可能 path.push_back(candidates[i]); sum += candidates[i]; //不用i+1了，表示可以重复读取当前的数 backtracking(candidates, target, sum, i); // 回溯 sum -= candidates[i]; path.pop_back(); } } public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { sort(candidates.begin(), candidates.end()); backtracking(candidates, target, 0, 0); return result; } };
👉组合总和 II👈
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。
本题数组 candidates 的元素是有重复的，而组合总和是无重复元素的数组 candidates。本道题的难点就是数组 candidates 有重复的元素，但不能有重复的组合，所以我们要在搜索的过程中去掉重复的组合。
所以的去重，就是使用过的元素不能重复选取。因为组合问题可以抽象成树形结构，那么使用过在树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。那么问题来了，我们所要的结果是同一树枝上使用过的还是同一树层上使用过的。
看一下题目的输出结果，一个组合中是可以有相同元素的，但是两个组合是不能够相同的。那么我们要去重的就是同一树层上使用过的，同一树枝上的都是一个组合里的元素，不需要去重。那么我们需要加一个 bool 类型数组 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 { private: vector<vector<int>> ret; vector<int> path; void BackTracking(const vector<int>& candidates, int target, int sum, int startIndex, vector<bool> used) { if(sum == target) { ret.push_back(path); return; } // 剪枝优化 for(size_t 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; used[i] = true; path.push_back(candidates[i]); sum += candidates[i]; // i+1表示一个数不能被重复选取 BackTracking(candidates, target, sum, i + 1, used); // 回溯 used[i] = false; path.pop_back(); sum -= candidates[i]; } } public: vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { ret.clear(); path.clear(); size_t n = candidates.size(); // 首先把给candidates排序，让其相同的元素都挨在一起。 sort(candidates.begin(), candidates.end()); vector<bool> used(n, false); BackTracking(candidates, target, 0, 0, used); return ret; } };
注：这直接用 startIndex 来去重也是可以的， 就不用used 数组了。
class Solution { private: vector<vector<int>> ret; vector<int> path; void BackTracking(const vector<int>& candidates, int target, int sum, int startIndex) { if(sum == target) { ret.push_back(path); return; } // 剪枝优化 for(size_t i = startIndex; i < candidates.size() && sum + candidates[i] <= target; ++i) { // 要对同一树层使用过的元素进行跳过 if(i > startIndex && candidates[i] == candidates[i - 1]) continue; path.push_back(candidates[i]); sum += candidates[i]; // i+1表示一个数不能被重复选取 BackTracking(candidates, target, sum, i + 1); // 回溯 path.pop_back(); sum -= candidates[i]; } } public: vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { ret.clear(); path.clear(); // 首先把给candidates排序，让其相同的元素都挨在一起。 sort(candidates.begin(), candidates.end()); BackTracking(candidates, target, 0, 0); return ret; } };
👉电话号码的字母组合👈
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
这道题是比较简单的，和上面的题的思路差不多，就不进行过多的讲解了，下面的代码有相应的注释。
class Solution { private: // 数字和字符串之间的映射可以采用哈希表 const string letterMap[10] = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" }; vector<string> ret; string str; void BackTracking(const string& digits, int startIndex) { // 当下标和digits.size()是说明可以收集结果了 if(startIndex == digits.size()) { ret.push_back(str); return; } int digit = digits[startIndex] - '0'; // 将字符'1'指向的数字1 string letters = letterMap[digit]; // 拿到数字对应的字符串 for(size_t i = 0; i < letters.size(); ++i) { str.push_back(letters[i]); //递归,startIndex+1表明一下层要处理下一个数字了 BackTracking(digits, startIndex + 1); str.pop_back(); } } public: vector<string> letterCombinations(string digits) { ret.clear(); str.clear(); if(digits.empty()) return ret; BackTracking(digits, 0); return ret; } };
class Solution { private: // letterMap是数字到字母串的映射 const string letterMap[10] = { "", // 0 "", // 1 "abc", // 2 "def", // 3 "ghi", // 4 "jkl", // 5 "mno", // 6 "pqrs", // 7 "tuv", // 8 "wxyz" // 9 }; vector<string> result; // index为递归的深度，也为digits数字串的下标 void backtracking(const string& digits, int index, const string& s) { // 收集结果 if(index == digits.size()) { result.push_back(s); return; } int digit = digits[index] - '0'; string letters = letterMap[digit]; // letters是数字对应的字母串 for(int i = 0; i < letters.size(); ++i) { backtracking(digits, index + 1, s + letters[i]); // 回到上一层是还是s } } public: vector<string> letterCombinations(string digits) { if(digits.size() == 0) { return result; } backtracking(digits, 0, ""); return result; } };
👉总结👈
本篇博客主要讲解了什么是回溯算法、回溯算法主要解决的问题、回溯算法的模板、组合问题以及剪枝优化等。那么以上就是本篇博客的全部内容了，如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家！💖💝❣️
