C++回溯法leetcode练习集-创新互联
- 什么是回溯法
- 回溯法的模板
- 组合
- 组合总和|||
- 洛谷刷题-八皇后问题
- 题目描述
- 输入格式
- 输出格式
- 样例 #1
- 样例输入 #1
- 样例输出 #1
- 提示
- 解析:
- 电话号码的字母组合
- 组合总和
- 组合总和II
- 分割回文串
- 复原IP地址
- 小结
- 子集
- 子集||
- 递增子序列
- 全排列
- 全排列||
- 842排列数字
- 皇后问题
回溯法可以叫做回溯搜索法,它是一种搜索方式
回溯是递归的副产品,只要有递归就会有回溯。
1.void backtracking(参数)
回溯函数终止条件
什么时候达到了终止条件,树中就可以看出,一般来说搜到叶子节点了,也就找到了满足条件的一条答案,把这个答案存放起来,并结束本层递归。
if (终止条件) {
存放结果;
return;
}
回溯法一般是在集合中递归搜索,集合的大小构成了树的宽度,递归的深度构成的树的深度。
for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
处理节点;
backtracking(路径,选择列表); // 递归
回溯,撤销处理结果
}
for循环可以理解为横向遍历
回溯算法模板框架
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
处理节点;
backtracking(路径,选择列表); // 递归
回溯,撤销处理结果
}
}
组合给定两个整数 n 和 k,返回 1 … n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
class Solution {
private:
vector>result;
vectorpath;
void backtracking(int n, int k, int startIndex) {
if(path.size() == k) {
result.push_back(path);
return;
}
for (int i = startIndex;i<=n;i++) {
path.push_back(i);
backtracking(n,k,i+1);
path.pop_back();
}
}
public:
vector>combine(int n, int k) {
backtracking(n,k,1);
return result;
}
};
组合总和|||找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。
说明:
所有数字都是正整数。
解集不能包含重复的组合。
示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]]
示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]
class Solution {
private:
vector>result;
vectorpath;
void backtracking(int targetSum, int k, int sum, int startIndex) {
if(sum>targetSum){
return;
}
if(path.size()==k) {
if(sum==targetSum)
result.push_back(path);
return;
}
for (int i = startIndex; i<= 9 - (k - path.size()) + 1; i++) { // 剪枝
sum += i; // 处理
path.push_back(i); // 处理
backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndex
sum -= i; // 回溯
path.pop_back(); // 回溯
}
}
public:
vector>combinationSum3(int k, int n) {
backtracking(n,k,0,1);
return result;
}
};
洛谷刷题-八皇后问题# [USACO1.5]八皇后 Checker Challenge
题目描述一个如下的$6 \times 6$
的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行、每列有且只有一个,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。
上面的布局可以用序列$2\ 4\ 6\ 1\ 3\ 5$
来描述,第$i$
个数字表示在第$i$
行的相应位置有一个棋子,如下:
行号$1\ 2\ 3\ 4\ 5\ 6$
列号$2\ 4\ 6\ 1\ 3\ 5$
这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出,解按字典顺序排列。
请输出前$3$
个解。最后一行是解的总个数。
一行一个正整数$n$
,表示棋盘是$n \times n$
大小的。
前三行为前三个解,每个解的两个数字之间用一个空格隔开。第四行只有一个数字,表示解的总数。
样例 #1 样例输入 #16
样例输出 #12 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4
提示【数据范围】
对于$100\%$
的数据,$6 \le n \le 13$
。
题目翻译来自NOCOW。
USACO Training Section 1.5
#include//个人不建议采用头文件,可能和定义的变量或名字起冲突,从而引起编译错误;
#include#include#includeusing namespace std;
int a[100],b[100],c[100],d[100];
//a数组表示的是行;
//b数组表示的是列;
//c表示的是左下到右上的对角线;
//d表示的是左上到右下的对角线;
int total;//总数:记录解的总数
int n;//输入的数,即N*N的格子,全局变量,搜索中要用
int print()
{
if(total<=2)//保证只输出前三个解,如果解超出三个就不再输出,但后面的total还需要继续叠加
{
for(int k=1;k<=n;k++)
cout>n;//输入N*N网格,n已在全局中定义
queen(1);//第一个皇后
cout<
解析:按三步骤来,1.递归函数的返回值以及参数 2.先想递归的终止情况 3.回溯搜索的遍历过程,就是for循环里面的树的宽度,递归的深度构成了树的深度。
1.定义四个数组分别表示行,列,两个对角线;参数就是quene(i+1)一直搜索。2.递归的终止情况就是每个a[i]都有位置,此时i>n的,就进一步打印3.j从1开始,代表列,如果纵和两个对角线都没有被占领才可以进去搜索,最后需要回溯,退一格。
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
17.电话号码的字母组合
示例: 输入:"23" 输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:尽管上面的答案是按字典序排列的,但是你可以任意选择答案输出的顺序
class Solution {
private:
const string letterMap[10]={
"",
"",
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz",
};
public:
vectorresult;
string s;
void backtracking(const string& digits, int index) {
if(index==digits.size()){
result.push_back(s);
return;
}
int digit = digits[index] - '0';
string letters = letterMap[digit];
for(int i=0;iletterCombinations(string digits) {
if(digits.size() == 0) {
return result;
}
backtracking(digits,0);
return result;
}
};
组合总和给你一个 无重复元素 的整数数组 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 。
仅有这两种组合。
class Solution {
private:
vector>result;
vectorpath;
void backtracking(vector& candidates,int target, int sum, int startIndex) {
if(sum >target) {
return;
}
if(sum==target)
{
result.push_back(path);
return;
}
for(int i= startIndex;i>combinationSum(vector& candidates, int target) {
backtracking(candidates,target,0,0);
return result;
}
};
组合总和II给定一个数组 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] ]
class Solution {
private:
vector>result;
vectorpath;
void backtracking(vector& candidates,int target, int sum,int startIndex ,vector& used){
if(sum>target)
return;
if(sum==target){
result.push_back(path);
return;
}
for(int i=startIndex;i0&&candidates[i]==candidates[i-1]&&used[i-1]==false){
continue;
}
sum+=candidates[i];
path.push_back(candidates[i]);
used[i] = true;
backtracking(candidates,target,sum,i+1,used);
used[i] = false;
sum-=candidates[i];
path.pop_back();
}
}
public:
vector>combinationSum2(vector& candidates, int target) {
vectorused(candidates.size(), false);
sort(candidates.begin(), candidates.end());
backtracking(candidates,target,0,0,used);
return result;
}
};
分割回文串给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例: 输入: "aab" 输出: [ ["aa","b"], ["a","a","b"] ]
class Solution {
private:
vector>result;
vectorpath; // 放已经回文的子串
void backtracking (const string& s, int startIndex) {
// 如果起始位置已经大于s的大小,说明已经找到了一组分割方案了
if (startIndex >= s.size()) {
result.push_back(path);
return;
}
for (int i = startIndex; i< s.size(); i++) {
if (isPalindrome(s, startIndex, i)) { // 是回文子串
// 获取[startIndex,i]在s中的子串
string str = s.substr(startIndex, i - startIndex + 1);
path.push_back(str);
} else { // 不是回文,跳过
continue;
}
backtracking(s, i + 1); // 寻找i+1为起始位置的子串
path.pop_back(); // 回溯过程,弹出本次已经填在的子串
}
}
bool isPalindrome(const string& s, int start, int end) {
for (int i = start, j = end; i< j; i++, j--) {
if (s[i] != s[j]) {
return false;
}
}
return true;
}
public:
vector>partition(string s) {
result.clear();
path.clear();
backtracking(s, 0);
return result;
}
};
复原IP地址给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。
有效的 IP 地址 正好由四个整数(每个整数位于 0 到 255 之间组成,且不能含有前导 0),整数之间用 '.' 分隔。
例如:"0.1.2.201" 和 "192.168.1.1" 是 有效的 IP 地址,但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效的 IP 地址。
示例 1:
输入:s = "25525511135"
输出:["255.255.11.135","255.255.111.35"]
示例 2:
输入:s = "0000"
输出:["0.0.0.0"]
示例 3:
输入:s = "1111"
输出:["1.1.1.1"]
示例 4:
输入:s = "010010"
输出:["0.10.0.10","0.100.1.0"]
示例 5:
输入:s = "101023"
输出:["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"
class Solution {
private:
vectorresult;// 记录结果
// startIndex: 搜索的起始位置,pointNum:添加逗点的数量
void backtracking(string& s, int startIndex, int pointNum) {
if (pointNum == 3) { // 逗点数量为3时,分隔结束
// 判断第四段子字符串是否合法,如果合法就放进result中
if (isValid(s, startIndex, s.size() - 1)) {
result.push_back(s);
}
return;
}
for (int i = startIndex; i< s.size(); i++) {
if (isValid(s, startIndex, i)) { // 判断 [startIndex,i] 这个区间的子串是否合法
s.insert(s.begin() + i + 1 , '.'); // 在i的后面插入一个逗点
pointNum++;
backtracking(s, i + 2, pointNum); // 插入逗点之后下一个子串的起始位置为i+2
pointNum--; // 回溯
s.erase(s.begin() + i + 1); // 回溯删掉逗点
} else break; // 不合法,直接结束本层循环
}
}
// 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法
bool isValid(const string& s, int start, int end) {
if (start >end) {
return false;
}
if (s[start] == '0' && start != end) { // 0开头的数字不合法
return false;
}
int num = 0;
for (int i = start; i<= end; i++) {
if (s[i] >'9' || s[i]< '0') { // 遇到非数字字符不合法
return false;
}
num = num * 10 + (s[i] - '0');
if (num >255) { // 如果大于255了不合法
return false;
}
}
return true;
}
public:
vectorrestoreIpAddresses(string s) {
result.clear();
if (s.size()< 4 || s.size() >12) return result; // 算是剪枝了
backtracking(s, 0, 0);
return result;
}
};
小结解题思路:
DFS 和回溯算法区别
DFS 是一个劲的往某一个方向搜索,而回溯算法建立在 DFS 基础之上的,但不同的是在搜索过程中,达到结束条件后,恢复状态,回溯上一层,再次搜索。因此回溯算法与 DFS 的区别就是有无状态重置
何时使用回溯算法
当问题需要 “回头”,以此来查找出所有的解的时候,使用回溯算法。即满足结束条件或者发现不是正确路径的时候(走不通),要撤销选择,回退到上一个状态,继续尝试,直到找出所有解为止
3.怎么样写回溯算法(从上而下,※代表难点,根据题目而变化)
①画出递归树,找到状态变量(回溯函数的参数),这一步非常重要※
②根据题意,确立结束条件
③找准选择列表(与函数参数相关),与第一步紧密关联※
④判断是否需要剪枝
⑤作出选择,递归调用,进入下一层
⑥撤销选择
给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1:
输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2:
输入:nums = [0]
输出:[[],[0]]
class Solution {
private:
vector>ans;
vectornum;
void backstracking(vector& nums,int start){
ans.push_back(num);
if(start>=nums.size())
return;
for(int i=start;istart&&num[i]==num[i-1])
// continue;
num.push_back(nums[i]);
backstracking(nums,i+1);
num.pop_back();
}
}
public:
vector>subsets(vector& nums) {
sort(nums.begin(),nums.end());
backstracking(nums,0);
return ans;
}
};
子集||给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。
示例:
输入: [1,2,2]
输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
class Solution {
private:
vector>ans;
vectornum;
void backtracking(vector& nums,int target) {
ans.push_back(num);
for(int i=target;itarget&&nums[i]==nums[i-1])
continue;
num.push_back(nums[i]);
backtracking(nums,i+1);
num.pop_back();
}
}
public:
vector>subsetsWithDup(vector& nums) {
sort(nums.begin(),nums.end());
backtracking(nums,0);
return ans;
}
};
总结:子集、组合类问题,关键是用一个 start 参数来控制选择列表!!
递增子序列给定一个整型数组, 你的任务是找到所有该数组的递增子序列,递增子序列的长度至少是2。
示例:
输入: [4, 6, 7, 7]
输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
说明:
给定数组的长度不会超过15。
数组中的整数范围是 [-100,100]。
给定数组中可能包含重复数字,相等的数字应该被视为递增的一种情况
// 版本一
class Solution {
private:
vector>result;
vectorpath;
void backtracking(vector& nums, int startIndex) {
if (path.size() >1) {
result.push_back(path);
// 注意这里不要加return,要取树上的节点
}
unordered_setuset; // 使用set对本层元素进行去重
for (int i = startIndex; i< nums.size(); i++) {
if ((!path.empty() && nums[i]< path.back())
|| uset.find(nums[i]) != uset.end()) {
continue;
}
uset.insert(nums[i]); // 记录这个元素在本层用过了,本层后面不能再用了
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
public:
vector>findSubsequences(vector& nums) {
result.clear();
path.clear();
backtracking(nums, 0);
return result;
}
};
全排列给定一个 没有重复 数字的序列,返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
class Solution {
public:
vector>result;
vectorpath;
void backtracking (vector& nums, vector& used) {
// 此时说明找到了一组
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for (int i = 0; i< nums.size(); i++) {
if (used[i] == true) continue; // path里已经收录的元素,直接跳过
used[i] = true; //标记过的元素本层循环不能用
path.push_back(nums[i]);
backtracking(nums, used);
path.pop_back();
used[i] = false;
}
}
vector>permute(vector& nums) {
result.clear();
path.clear();
vectorused(nums.size(), false);
backtracking(nums, used);
return result;
}
};
每层都是从0开始搜索而不是startIndex
需要used数组记录path里都放了哪些元素了
给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。
示例 1:
输入:nums = [1,1,2]
输出: [[1,1,2], [1,2,1], [2,1,1]]
示例 2:
输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
class Solution {
private:
vector>result;
vectorpath;
void backtracking (vector& nums, vector& used) {
// 此时说明找到了一组
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for (int i = 0; i< nums.size(); i++) {
// used[i - 1] == true,说明同一树枝nums[i - 1]使用过
// used[i - 1] == false,说明同一树层nums[i - 1]使用过
// 如果同一树层nums[i - 1]使用过则直接跳过
if (i >0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
continue;
}
if (used[i] == false) {
used[i] = true;
path.push_back(nums[i]);
backtracking(nums, used);
path.pop_back();
used[i] = false;
}
}
}
public:
vector>permuteUnique(vector& nums) {
result.clear();
path.clear();
sort(nums.begin(), nums.end()); // 排序
vectorused(nums.size(), false);
backtracking(nums, used);
return result;
}
};
比全排列多了个去重步骤
842排列数字给定一个整数 n,将数字 1∼n 排成一排,将会有很多种排列方法。
现在,请你按照字典序将所有的排列方法输出。
输入格式
共一行,包含一个整数 n。
输出格式
按字典序输出所有排列方案,每个方案占一行。
数据范围
1≤n≤7
输入样例:
3
输出样例:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
#include#include#include
using namespace std;
const int N = 10;
int n,path[N];//存储一条下来的数字
bool st[N]; //存当前位置有没有被用过
void dfs(int u) {
if(u==n)
{
for(int i = 0;i>n;
dfs(0);
return 0;
}
皇后问题n−皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上,使得皇后不能相互攻击到,即任意两个皇后都不能处于同一行、同一列或同一斜线上。
现在给定整数 n,请你输出所有的满足条件的棋子摆法。
输入格式
共一行,包含整数 n。
输出格式
每个解决方案占 n 行,每行输出一个长度为 n 的字符串,用来表示完整的棋盘状态。
其中 . 表示某一个位置的方格状态为空,Q 表示某一个位置的方格上摆着皇后。
每个方案输出完成后,输出一个空行。
注意:行末不能有多余空格。
输出方案的顺序任意,只要不重复且没有遗漏即可。
数据范围
1≤n≤9
输入样例:
4
输出样例:
.Q…
…Q
Q…
…Q.
…Q.
Q…
…Q
.Q…
#include#include#include
using namespace std;
const int N =20;
int n;
bool col[N],dg[N],udg[N]; //列,对角线,反对角线
char g[N][N];//输出
void dfs(int u) {
if(u==n)//当u走到最后一行
{
for(int i=0;i>n;
for(int i=0;i
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
网站标题:C++回溯法leetcode练习集-创新互联
本文地址:http://myzitong.com/article/dscgdc.html