搜索引擎优化是免费的吗,北京seo包年,互联网设计师leader,怀化做网站的公司算法学习——LeetCode力扣回溯篇2 40. 组合总和 II
40. 组合总和 II - 力扣#xff08;LeetCode#xff09;
描述
给定一个候选人编号的集合 candidates 和一个目标数 target #xff0c;找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字…算法学习——LeetCode力扣回溯篇2 40. 组合总和 II
40. 组合总和 II - 力扣LeetCode
描述
给定一个候选人编号的集合 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意解集不能包含重复的组合。
示例
示例 1:
输入: candidates [10,1,2,7,6,1,5], target 8, 输出: [ [1,1,6], [1,2,5], [1,7], [2,6] ]
示例 2:
输入: candidates [2,5,2,1,2], target 5, 输出: [ [1,2,2], [5] ]
提示
1 candidates.length 1001 candidates[i] 501 target 30
代码解析
和39的区别是不能重复使用元素
回溯无去重超时
无去重只能在最后加入时候find查找是否存在一样再加入
class Solution {
public:vectorvectorint result;vectorint path;void backtarcking(vectorint candidates, int target , int sum ,int indnx){if(sum target)return;if(sum target){auto it find(result.begin(),result.end(),path);if(it result.end() ) result.push_back(path);return;}for(int iindnx ; i candidates.size() sum candidates[i] target ; i){path.push_back(candidates[i]);backtarcking(candidates,target,sumcandidates[i],i1);path.pop_back();}return;}vectorvectorint combinationSum2(vectorint candidates, int target) {sort(candidates.begin(),candidates.end());backtarcking(candidates,target,0,0);return result;}
};
回溯去重 去重在同一层上值一样的元素只能用一次。同一枝上可以多次用
class Solution {
public:vectorvectorint result;vectorint path;void backtarcking(vectorint candidates, int target , int sum ,int indnx){if(sum target)return;if(sum target){result.push_back(path);return;}for(int iindnx ; i candidates.size() sum candidates[i] target ; i){//发现一样的元素这一层已经用过了直接跳过这次if(i indnx candidates[i] candidates[i-1]) continue;path.push_back(candidates[i]);backtarcking(candidates,target,sumcandidates[i],i1);path.pop_back();}return;}vectorvectorint combinationSum2(vectorint candidates, int target) {sort(candidates.begin(),candidates.end());backtarcking(candidates,target,0,0);return result;}
};
131. 分割回文串
131. 分割回文串 - 力扣LeetCode
描述
给你一个字符串 s请你将 s 分割成一些子串使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例
示例 1
输入s “aab” 输出[[“a”,“a”,“b”],[“aa”,“b”]]
示例 2
输入s “a” 输出[[“a”]]
提示
1 s.length 16s 仅由小写英文字母组成
代码解析
class Solution {
public:vectorvectorstring result;//判断字串是否是回文串bool check(const string s){for(int i0 ; is.size()/2 ; i){if(s[i] ! s[s.size()- 1 -i]) return false;}return true;}void backtracking(string s , int indnx ,vectorstring path){//当循环指针大于等于最大值的时候认为分割出一种结果if(indnx s.size()){result.push_back(path);return;}//循环字符串长度从index当前的运行指针开始切割回文串for(int i indnx ; is.size() ;i ){string tmp;//切割字串字串是indnx到i之间。for(int j indnx ; j i ;j){tmp s[j];}// couttmpendl;//检验字串是否为回文串是回文串压入路径不是i1进行下一个长度加1的字串if(check(tmp)1) path.push_back(tmp);else continue;//如果当前字串是回文串递归indnx加1backtracking(s,i1,path);//回溯弹出上一个字串path.pop_back();}return;}vectorvectorstring partition(string s) {if(s.size()0) return result;vectorstring path;backtracking(s,0,path);return result;}
};
93. 复原 IP 地址
93. 复原 IP 地址 - 力扣LeetCode
描述
有效 IP 地址 正好由四个整数每个整数位于 0 到 255 之间组成且不能含有前导 0整数之间用 ‘.’ 分隔。
例如“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址但是 “0.011.255.245”、“192.168.1.312” 和 “192.1681.1” 是 无效 IP 地址。 给定一个只包含数字的字符串 s 用以表示一个 IP 地址返回所有可能的有效 IP 地址这些地址可以通过在 s 中插入 ‘.’ 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
示例
示例 1
输入s “25525511135” 输出[“255.255.11.135”,“255.255.111.35”]
示例 2
输入s “0000” 输出[“0.0.0.0”]
示例 3
输入s “101023” 输出[“1.0.10.23”,“1.0.102.3”,“10.1.0.23”,“10.10.2.3”,“101.0.2.3”]
提示
1 s.length 20s 仅由数字组成
代码解析
class Solution {
public:vectorstring result;vectorstring path;//判断是合法IPbool cheak(string s){if(s.size()0)return false;if(s.size() 1 s[0]0) return false;if (stoi(s) 255) return false;return true;}void back_tracking(string s , int indnx ){//IP最大短是4if(path.size() 4) return;//循环指针大于等于长度并且IP段为四段。合法IPif(indnx s.size() path.size()4){string tmp;for(int i0 ;i path.size()-1 ;i){tmp path[i];tmp .;}tmp path[path.size()-1];result.push_back(tmp);return;}//循环输入字符串从index开始截取IP段for(int iindnx ; is.size() ;i){string tmp;//截取一个IP段但是不超过3位for(int j indnx ; ji (j-indnx)3 ;j){tmp s[j];}//检测是否为合法段合法压入路径不合法跳过该段if(cheak(tmp)1) path.push_back(tmp);else continue;//递归back_tracking(s,i1);//回溯path.pop_back();}return;}vectorstring restoreIpAddresses(string s) {back_tracking(s,0);return result;}
};
78. 子集
78. 子集 - 力扣LeetCode
描述
给你一个整数数组 nums 数组中的元素 互不相同 。返回该数组所有可能的子集幂集。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例
示例 1
输入nums [1,2,3] 输出[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2
输入nums [0] 输出[[],[0]]
提示
1 nums.length 10-10 nums[i] 10nums 中的所有元素 互不相同
代码解析 与中序遍历N叉树非常的类似 每一个子集就是一个节点遍历所有的节点
回溯遍历法不要简单问题复杂化
class Solution {
public:vectorvectorint result;vectorint path;void backtracking(vectorint nums , int indnx ){//每一个节点都加入无须判断节点result.push_back(path);//如果遍历指针大于等于最深处就返回if(indnx nums.size()) return;//横向循环for(int iindnx ; i nums.size() ; i ){//新值压入path.push_back(nums[i]);backtracking(nums,i1);//递归path.pop_back();//回溯}return;}vectorvectorint subsets(vectorint nums) {backtracking(nums,0);return result;}
};
90. 子集 II
90. 子集 II - 力扣LeetCode
描述
给你一个整数数组 nums 其中可能包含重复元素请你返回该数组所有可能的子集幂集。
解集 不能 包含重复的子集。返回的解集中子集可以按 任意顺序 排列。
示例
示例 1
输入nums [1,2,2] 输出[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2
输入nums [0] 输出[[],[0]]
提示
1 nums.length 10-10 nums[i] 10
代码解析 去重分为层次去重和树枝去重
层次去重 是一个元素只能用一次一样的两个可以用两次【122】两个2各自可用一次。 if (i indnx nums[i] nums[i - 1] ) continue; 当前的和上一个相同就跳过树枝去重 是数值一样的元素只能用一个一样的两个元素也只能用一次。【122】两个2只能用一个2 回溯去重
class Solution {
public:vectorvectorint result;vectorint path;int pre;void backtracking(vectorint nums , int indnx){result.push_back(path);if(indnx nums.size())return;for(int i indnx ; i nums.size() ; i){if (i indnx nums[i] nums[i - 1] ) { continue;}path.push_back(nums[i]);backtracking(nums , i1);path.pop_back();}return;}vectorvectorint subsetsWithDup(vectorint nums) {sort(nums.begin(),nums.end());backtracking(nums,0);return result;}
};
