域名大全免费网站,网站开发工程师岗位,网站logo是什么,哈尔滨建站模板系统39. 组合总和
力扣题目链接(opens new window)
给定一个无重复元素的数组 candidates 和一个目标数 target #xff0c;找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明#xff1a;
所有数字#xff08;包括 ta…39. 组合总和
力扣题目链接(opens new window)
给定一个无重复元素的数组 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明
所有数字包括 target都是正整数。解集不能包含重复的组合。
示例 1
输入candidates [2,3,6,7], target 7,所求解集为 [ [7], [2,2,3] ]
示例 2
输入candidates [2,3,5], target 8,所求解集为 [ [2,2,2,2], [2,3,3], [3,5] ] 思路 本题搜索的过程抽象成树形结构如下 注意图中叶子节点的返回条件因为本题没有组合数量要求仅仅是总和的限制所以递归没有层数的限制只要选取的元素总和超过target就返回 本题还需要startIndex来控制for循环的起始位置对于组合问题什么时候需要startIndex呢如果是一个集合来求组合的话就需要startIndex如果是多个集合取组合各个集合之间相互不影响那么就不用startIndex class Solution {
private:vectorvectorint result;vectorint path;void backtracking(vectorint 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(); i) {sum candidates[i];path.push_back(candidates[i]);// 纵向遍历树结构backtracking(candidates, target, sum, i); // 不用i1了表示可以重复读取当前的数sum - candidates[i];//回溯path.pop_back();}}
public:vectorvectorint combinationSum(vectorint candidates, int target) {result.clear();path.clear();backtracking(candidates, target, 0, 0);return result;}
}; 40.组合总和II
力扣题目链接(opens new window)
给定一个数组 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明 所有数字包括目标数都是正整数。解集不能包含重复的组合。
示例 1:输入: candidates [10,1,2,7,6,1,5], target 8,所求解集为:
[[1, 7],[1, 2, 5],[2, 6],[1, 1, 6]
]示例 2:输入: candidates [2,5,2,1,2], target 5,所求解集为:
[[1,2,2],[5]
] 思路: 这道题目和39.组合总和 (opens new window)如下区别 本题candidates 中的每个数字在每个组合中只能使用一次。本题数组candidates的元素是有重复的而39.组合总和 (opens new window)是无重复元素的数组candidates 最后本题和39.组合总和 (opens new window)要求一样解集不能包含重复的组合。 本题的难点在于区别2中集合数组candidates有重复元素但还不能有重复的组合。 一些同学可能想了我把所有组合求出来再用set或者map去重这么做很容易超时 所以要在搜索的过程中就去掉重复组合。 我们要去重的是同一树层上的“使用过”同一树枝上的都是一个组合里的元素不用去重。 为了理解去重我们来举一个例子candidates [1, 1, 2], target 3方便起见candidates已经排序了 强调一下树层去重的话需要对数组排序 选择过程树形结构如图所示 与39.组合总和 (opens new window)套路相同此题还需要加一个bool型数组used用来记录同一树枝上的元素是否使用过。 这个集合去重的重任就是used来完成的。 前面我们提到要去重的是“同一树层上的使用过”如何判断同一树层上元素相同的元素是否使用过了呢。 如果candidates[i] candidates[i - 1] 并且 used[i - 1] false就说明前一个树枝使用了candidates[i - 1]也就是说同一树层使用过candidates[i - 1]。 此时for循环里就应该做continue的操作。 在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:vectorintpath;vectorvectorintresult;// int sum0;void backtracking(vectorint candidates, int target, int sum, int startIndex, vectorbool used){//终止条件if(sumtarget) {result.push_back(path);return;}if(sumtarget)return;//横向遍历树状结构// sumcandidates[i]target是为了剪枝剪去不必要的遍历for(int i startIndex; i candidates.size() sum candidates[i] target; i){//同层去重if(i0candidates[i]candidates[i-1]used[i-1]false){continue;}sumcandidates[i];path.push_back(candidates[i]);used[i]true;backtracking(candidates, target, sum, i1, used);//纵向遍历递归i1开始因为不可重复选择同一元素//回溯sum-candidates[i];path.pop_back();used[i]false;}}vectorvectorint combinationSum2(vectorint candidates, int target) {vectorboolused(candidates.size(), false);path.clear();result.clear();sort(candidates.begin(), candidates.end());backtracking(candidates, target, 0, 0, used);return result;}
}; 9.分割回⽂串
131. 分割回文串 - 力扣LeetCode
给你一个字符串 s请你将 s 分割成一些子串使每个子串都是 回文串。返回 s 所有可能的分割方案。
示例 1
输入s aab
输出[[a,a,b],[aa,b]]示例 2
输入s a
输出[[a]]提示
1 s.length 16s 仅由小写英文字母组成 思路:本题这涉及到两个关键问题 1. 切割问题有不同的切割⽅式 2. 判断回⽂ 我们来分析⼀下切割其实切割问题类似组合问题。 例如对于字符串abcdef 组合问题选取⼀个a之后在bcdef中再去选取第⼆个选取b之后在cdef中再选取第三个.....。 切割问题切割⼀个a之后在bcdef中再去切割第⼆段切割b之后在cdef中再切割第三段..... 所以切割问题也可以抽象为⼀棵树形结构 全局变量数组path存放切割后回⽂的⼦串⼆维数组result存放结果集。 这两个参数可以放到函数参数⾥ 本题递归函数参数还需要startIndex因为切割过的地⽅不能重复切割和组合问题也是保持⼀致的。 终止条件切割线切到了字符串最后⾯说明找到了⼀种切割⽅法此时就是本层递归的终⽌条 件 class Solution {
public:vectorstringpath;vectorvectorstringresult;void backtracking(string s, int startIndex){if(startIndexs.size()){//递归结束条件result.push_back(path);}//横向遍历树状结构for(int istartIndex;is.size();i){if(isPalindrome(s, startIndex, i)){//判断是否为回文字符串//截取回文串string str s.substr(startIndex, i-startIndex1);path.push_back(str);}else continue;//纵向遍历树结构backtracking(s,i1);path.pop_back();//回溯}}bool isPalindrome(string s, int startIndex, int endIndex){for(int istartIndex,jendIndex;ij;i,j--){if(s[i]!s[j]) return false;}return true;}vectorvectorstring partition(string s) {result.clear();path.clear();backtracking(s,0);return result;}
}; 参考代码随想录
