在建设局网站上怎么样总监解锁,做网站干什么用,大品牌网站建设,品牌网站开发特点Leetcode 216.组合总和III
题目链接#xff1a;216 组合总和III 题干#xff1a;找出所有相加之和为 n 的 k 个数的组合#xff0c;且满足下列条件#xff1a; 只使用数字1到9每个数字 最多使用一次 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次#…Leetcode 216.组合总和III
题目链接216 组合总和III 题干找出所有相加之和为 n 的 k 个数的组合且满足下列条件 只使用数字1到9每个数字 最多使用一次 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次组合可以以任何顺序返回。 2 k 91 n 60 思考回溯法。先设计全局变量结果集result路径集path。再考虑回溯函数 函数返回值以及参数 参数含义k满足条件的组合内数的个数targetSum满足条件的组合内数相加之和sum当前路径内数相加之和startIndex下一层循环搜索的起始位置
终止条件在路径path 满足条件长度k后判断当前sum是否满足targetSum若满足则添加到容器result内。
单层搜索逻辑从startIndex开始循环添加到路径path中再递归处理最后再回溯。
剪枝优化处理
若for循环选择的起始位置之后的元素个数已经不足需要的元素个数则后序数就没有必要搜索for循环中若加入当前数sum值超过目标值targetSum则后序数就没有必要搜索
代码
class Solution {
public:vectorvectorint result;vectorint path;void backtracking(int k, int targetSum, int sum, int startIndex) {if (path.size() k) {if (sum targetSum)result.push_back(path);return;}for (int i startIndex; i 9 - (k - path.size()) 1; i) {//剪枝操作若当前数加入路径后相加之和大于目标值则结束循环if (sum i targetSum) break;else {sum i;path.push_back(i);backtracking(k, targetSum, sum, i 1);//回溯sum - i;path.pop_back();}}}vectorvectorint combinationSum3(int k, int n) {result.clear();path.clear();backtracking(k, n, 0, 1);return result;}
};
Leetcode 17.电话号码的字母组合
题干链接17 电话号码的字母组合 题干给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。 0 digits.length 4digits[i] 是范围 [2, 9] 的一个数字。 思考回溯法。先定义静态数字与字母的映射表全局变量结果集result路径集path。再考虑回溯函数
函数返回值以及参数 参数含义digits题干给定字符串index字符串中某个字符的下标
终止条件若当前遍历到字符串最后一个字符则将路径path加入结果集result。
单层搜索逻辑先取出当前处理数字对应的字母集再循环处理该字母集中的字符添加到路径递归处理回溯移除路径。
代码
class Solution {
public:const string letterMap[10] { //数字与字母的映射表, , //0、1abc, def, //2、3ghi, jkl, //4、5mno, pqrs, //6、7tuv, wxyz //8、9};vectorstring result;string path;void backtracking(string digits, int index) {if (index digits.size()) {result.push_back(path);return;}string s letterMap[digits[index] - 0]; //取当前处理数字对应的字母集for (int i 0; i s.size(); i) {path s[i];backtracking(digits, index 1);path.pop_back(); //回溯}}vectorstring letterCombinations(string digits) {result.clear();if (digits.size() 0) return result;path ;backtracking(digits, 0);return result;}
};
自我总结
熟悉回溯三部曲for循环横向遍历递归纵向遍历回溯不断调整结果集。
