手机网站建设liedns,嘉兴网站建设托管,开发者模式小米,商城和营销型网站建设40.组合II 给定一个候选人编号的集合 candidates 和一个目标数 target #xff0c;找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意#xff1a;解集不能包含重复的组合。 思路:组合题目二#xff0c;这个题…40.组合II 给定一个候选人编号的集合 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意解集不能包含重复的组合。 思路:组合题目二这个题目与组合一的区别在于本题目中的candidates的每个元素只能使用一次而且本题中的candidate数组中会有重复的元素。要对此进行去重
首先定义三个成员变量一维和二维的数组和sumsum代表累加的和。在回溯函数中如果当前的sum和等于目标值将结果放到二维数组中并返回。然后继续往下看通过for循环遍历目标数组(此时在for的循环条件里加入了剪枝的操作当 当前的和加上当前对应的数组值小于等于目标值才可以继续进入循环否则的话就不进入循环因为不满足条件进入循环也没必要了)如果i大于0(不能是第一层)并且当前对应的数组的值不能等于前一个值如果相等在遍历这第二个相同的值就没有意义了因为前一个值所遍历的范围已经包含第二个值了所以应该将第二个去重掉(在这道题目中我定义了一个存储布尔类型的动态数组并且它的大小与candidate的大小相同来记录已经遍历过的元素如果元素已经使用过就设置为TRUE),在if条件中判断如果当前值与前一个相等并且前一个的used数组显示为FALSE。为什么一定是等于FALSE呢等于TRUE不可以吗?如果等于TRUE的话我们可能会遗漏一些正确的组合如下图所示: 而我们实际要剪枝的是:也就是Carl哥说的树层和树枝去重(下图是树层上图是树枝) 去重的条件大概就是这些然后呢就是正常的回溯递归注意还有一点的是我们依然采用了startIndex来更新递归后的搜索初始节点进行去重。
class Solution {
public:
vectorint path;
vectorvectorint res;
int sum;void travelBacking(vectorint candidates, int target,int startIndex,vectorbool used){if(sumtarget){res.push_back(path);return ;}for(int istartIndex;icandidates.size()sumcandidates[i]target;i){if(i0used[i-1]falsecandidates[i]candidates[i-1]){continue;}sumcandidates[i];path.push_back(candidates[i]);used[i]true;travelBacking(candidates,target,i1,used);//每个数字在每个组合中只能使用一次used[i]false;sum-candidates[i];path.pop_back();}}
public:vectorvectorint combinationSum2(vectorint candidates, int target) {int startIndex0;vectorbool used(candidates.size(),false);sort(candidates.begin(),candidates.end());travelBacking(candidates,target,startIndex,used);return res;}
};
131.分割回文串 给你一个字符串 s请你将 s 分割成一些子串使每个子串都是 回文串。 返回 s 所有可能的分割方案。 思路:分割字符串第一眼看似很难但实际上与前面的组合题目很像的需要增加的操作就是要定义一个判断回文串的函数然后正常定义回溯函数如果传入的startIndex要大于等于字符串长度startIndex代表切割线如果切割线等于字符串长度代表切割到尾部了将path存入result并返回这是回溯三部曲的第二步确认回溯终止条件第一步是传入参数第三步是确认单层递归逻辑首先判断当前子串是否为回文串如果是回文串进入循环将其截取出来并存入字符串str中注意截取时传入的参数是startIndex--字符串的起始位置和长度--i-startIndex1,因为长度就是下标加1如果非回文串的话continue(continue 语句用于跳过当前循环的剩余部分并立即开始下一次循环迭代)注意有人可能不理解为什么开始值和结束值是startIndex和i呢? startIndex是起始位置而i则是结束位置。
class Solution {
public:
vectorstring path;
vectorvectorstring result;bool isPartition(string s,int start,int end){//判断是否为回文串for(int istart,jend;ij;i,j--){if(s[i]!s[j]){return false;}}return true;}void travelBacking(string s,int startIndex){if(startIndexs.size()){result.push_back(path);return;}for(int istartIndex;is.size();i){if(isPartition(s,startIndex,i)){string strs.substr(startIndex,i-startIndex1);path.push_back(str);}else{continue;}travelBacking(s,i1);path.pop_back();}}vectorvectorstring partition(string s) {travelBacking(s, 0);return result;}
};
78.子集 给你一个整数数组 nums 数组中的元素 互不相同 。返回该数组所有可能的 子集 幂集。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 思路:此题相对于上面的题目来说算是简单的了同样的回溯模版差别在于在它是取所有的集合要在回溯函数开始时将path加入到二维数组中然后正常将该题目抽象成树形结构遍历。如图所示:选自代码随想录图解 class Solution {
public:
vectorint path;
vectorvectorint res;void travelBacking(vectorint nums,int startIndex){res.push_back(path);if(startIndexnums.size()){return;}for(int istartIndex;inums.size();i){path.push_back(nums[i]);travelBacking(nums,i1); path.pop_back();}}
public:vectorvectorint subsets(vectorint nums) {travelBacking(nums,0);return res;}
};
90.子集II 给你一个整数数组 nums 其中可能包含重复元素请你返回该数组所有可能的 子集 幂集。 解集 不能 包含重复的子集。返回的解集中子集可以按 任意顺序 排列。 思路: 和上一道题很像主要就是和组合二大体思路的去重树层去重和树枝去重通过一个used数组来记录是否使用过这个数字当当前的值与前一个值相等时并且前一个值为FALSE代表是树层去重无需遍历当前的树枝了因为前面的树枝遍历已经包含了这个的树枝遍历还需要注意的一点是因为子集是找出所以的组合并记录所以要在回溯函数开头将一维数组存到二维数组中。
class Solution {
public:
vectorint path;
vectorvectorint res;void travelBacking(vectorint nums,int startIndex,vectorbool used){res.push_back(path);if(startIndexnums.size()){return;}for(int istartIndex;inums.size();i){if(i0nums[i]nums[i-1]used[i-1]false){continue;}path.push_back(nums[i]);used[i]true;travelBacking(nums,i1,used);used[i]false;path.pop_back();}}
public:vectorvectorint subsetsWithDup(vectorint nums) {vectorbool used(nums.size(),false);sort(nums.begin(),nums.end());travelBacking(nums,0,used);return res;}
};
