俄罗斯门户网站,菏泽建设,深圳微商城网站设计价格,佛山企业做网站回溯法
前 言
回溯法也可以叫做回溯搜索法#xff0c;它是一种搜索的方式。回溯是递归的副产品#xff0c;只要有递归就会有回溯。回溯法#xff0c;一般可以解决如下几种问题#xff1a;
组合问题#xff1a;N个数里面按一定规则找出k个数的集合切割问题#xff1a;一…回溯法
前 言
回溯法也可以叫做回溯搜索法它是一种搜索的方式。回溯是递归的副产品只要有递归就会有回溯。回溯法一般可以解决如下几种问题
组合问题N个数里面按一定规则找出k个数的集合切割问题一个字符串按一定规则有几种切割方式子集问题一个N个数的集合里有多少符合条件的子集排列问题N个数按一定规则全排列有几种排列方式棋盘问题N皇后解数独等等
回溯法模板: void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果}
}77. 组合
给定两个整数 n 和 k返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1
输入n 4, k 2
输出
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]示例 2
输入n 1, k 1
输出[[1]]解题 class Solution {
public:vectorvectorint res;// 存放符合条件结果的集合vectorint path;// 用来存放符合条件结果void assemble(int n, int k, int index){if(path.size()k){res.push_back(path);//存放结果return;}//剪枝处理in-(k-path.size())1for(int iindex; in-(k-path.size())1; i){//不剪枝就是 … in …path.push_back(i); // 处理节点assemble(n, k, i1);// 递归path.pop_back();// 回溯撤销处理的节点}return;}vectorvectorint combine(int n, int k) {assemble(n, k, 1);return res;}
};216. 组合总和 III
找出所有相加之和为 n 的 k 个数的组合且满足下列条件
只使用数字1到9每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次组合可以以任何顺序返回。
示例 1:
输入: k 3, n 7
输出: [[1,2,4]]
解释:
1 2 4 7
没有其他符合的组合了。示例 2:
输入: k 3, n 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 2 6 9
1 3 5 9
2 3 4 9
没有其他符合的组合了。class Solution {
public:vectorvectorint res;vectorint path;void find(int k, int n, int sum, int index){if(sumn) return;//剪枝处理if(path.size()k sum n){res.push_back(path);return;}for(int iindex; i9-(k-path.size())1; i){//剪枝处理避免相同元素重复操作sumi;path.push_back(i);find(k,n,sum,i1);sum-i; path.pop_back();}return;}vectorvectorint combinationSum3(int k, int n) {find(k,n,0,1);return res;}
};17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。 示例 1
输入digits 23
输出[ad,ae,af,bd,be,bf,cd,ce,cf]示例 2
输入digits
输出[]class Solution {
public:vectorstring res;string find;const vectorstring anjian{ , , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz};//需要设计一个存放号码对应字符的数组void phoneStr(string digits, int length){if(lengthdigits.size()){res.push_back(find);return;}string keyValanjian[digits[length]-0];for(int i0; ikeyVal.size(); i){//不需要剪枝处理一个个列举find.push_back(keyVal[i]);phoneStr(digits, length1);find.pop_back();}}vectorstring letterCombinations(string digits) {if(digits.empty()) return{};phoneStr(digits, 0);return res;}
};39. 组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同则两种组合是不同的。
对于给定的输入保证和为 target 的不同组合数少于 150 个。
示例 1
输入candidates [2,3,6,7], target 7
输出[[2,2,3],[7]]
解释
2 和 3 可以形成一组候选2 2 3 7 。注意 2 可以使用多次。
7 也是一个候选 7 7 。
仅有这两种组合。示例 2
输入: candidates [2,3,5], target 8
输出: [[2,2,2,2],[2,3,3],[3,5]]注意index的使用 class Solution {
public:vectorvectorint res;vectorint path;void find(vectorint candidates, int target, int sum, int index){if(sumtarget){return;}if(sumtarget){res.push_back(path);return;}//iindex是为了保证输出的都是有序的数组确保输出结果的唯一性for(int iindex; icandidates.size(); i){//剪枝处理就是先在主函数对candidates排序然后判断sum candidates[i] target;sumcandidates[i];path.push_back(candidates[i]);find(candidates, target, sum, i);//如果是(i1), 则保证了输出结果每个元素的唯一性sum-candidates[i];path.pop_back();}}vectorvectorint combinationSum(vectorint candidates, int target) {find(candidates, target, 0, 0);return res;}
};40. 组合总和 II
给定一个候选人编号的集合 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]
]class Solution {
public:vectorvectorint res;vectorint path;void find(vectorint candidates, int target, int index, int sum){if(sumtarget) {return;}//剪枝if(sumtarget){res.push_back(path);return;}for(int i index; icandidates.size()sumcandidates[i]target; i){剪枝//子树里可以不跳过,同一层树里跳过相同元素if(iindex candidates[i]candidates[i-1]) {continue;}sumcandidates[i];path.push_back(candidates[i]); find(candidates, target, i1, sum);//index1保证每个数只用一次sum-candidates[i];path.pop_back();}}vectorvectorint combinationSum2(vectorint candidates, int target) {sort(candidates.begin(), candidates.end());find(candidates, target, 0, 0);return res;}
};131. 分割回文串
给你一个字符串 s请你将 s 分割成一些子串使每个子串都是 回文串。返回s所有可能的分割方案。
示例 1
输入s aab
输出[[a,a,b],[aa,b]]示例 2
输入s a
输出[[a]]class Solution {
public:vectorvectorstring res;vectorstring path;void backfind(string s, int index){//通过index进行切割if(indexs.size()){res.push_back(path);return;}for(int iindex; is.size(); i){if(isHuiwen(s,index,i)){string strs.substr(index, i-index1);//index是留给后面元素开头用的所以这里不包含i故1path.push_back(str);backfind(s,i1);path.pop_back();}else{continue;}}}bool isHuiwen(string s, int begin, int end){//判断回文for(int ibegin,jend; ij; i, j--){if(s[i]!s[j]){return false;}}return true;}vectorvectorstring partition(string s) {backfind(s, 0);return res;}
};93. 复原 IP 地址
有效 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]class Solution {
public:vectorstring res;//存放结果int pointnum0;//加入的.数量void backFindip(string s, int index){if(pointnum3){//加入的.数量为3个已分割出4段了if(ifIPnum(s,index,s.size()-1)){//判断剩下一段字符是否合个res.push_back(s);return;}return;}for(int iindex; is.size(); i){if(ifIPnum(s,index,i)){//如果这个字符串合格pointnum;s.insert(s.begin()i1,.);//会在这个后面加上.进行分割backFindip(s, i2);//递归因为插入. 所以2跳到.的后面pointnum--;//回溯s.erase(s.begin()i1);//回溯去除.}}}bool ifIPnum(string s, int begin, int end){if (begin end) return false;//防止越界关键if(s[begin]0 begin ! end){return false;//判断前导0}int num0;for(int ibegin; iend; i){if(s[i]9||s[i]0){return false;}num num*10 (s[i]-0);if(num255){return false;}}return true;}vectorstring restoreIpAddresses(string s) {backFindip(s,0);return res;}
};78. 子集
给你一个整数数组 nums 数组中的元素 互不相同 。返回该数组所有可能的子集幂集。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1
输入nums [1,2,3]
输出[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]示例 2
输入nums [0]
输出[[],[0]]class Solution {
public:vectorvectorint res;vectorint path;void find(vectorint nums, int index){if(indexnums.size()){return;}for(int iindex; inums.size(); i){path.push_back(nums[i]);res.push_back(path);find(nums, i1);path.pop_back();}return;}vectorvectorint subsets(vectorint nums) {res.push_back(path);find(nums,0);return res;}
};90. 子集 II
给你一个整数数组 nums 其中可能包含重复元素请你返回该数组所有可能的 子集幂集。
解集 不能 包含重复的子集。返回的解集中子集可以按 任意顺序 排列。
示例 1
输入nums [1,2,2]
输出[[],[1],[1,2],[1,2,2],[2],[2,2]]示例 2
输入nums [0]
输出[[],[0]]class Solution {
public:vectorvectorint res;vectorint path;void backfind(vectorint nums, int index, vectorbool used){if(indexnums.size()){return;}for(int iindex; inums.size(); i){if(i0nums[i]nums[i-1]used[i-1]false){continue;}//去重里面的used判断必须是used[i-1]false是上一个的path.push_back(nums[i]);res.push_back(path);used[i]true;//used放的是i不是nums[i]backfind(nums, i1, used);path.pop_back();used[i]false;}return;}vectorvectorint subsetsWithDup(vectorint nums) {sort(nums.begin(), nums.end());vectorbool used(nums.size(),false);res.push_back(path);backfind(nums, 0, used);return res;}
};
