C++回溯

1、回溯常见模板

/*
	回溯法模板
	def func():
		if 满足条件:
			return result
		for range 选择列表:
			选择
			func()
			撤销选择
*/

代码示例：1.求 1~n 的全排列并打印出来。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+5;
int n;
int a[N],vis[N];
void dfs(int dep){
	if(dep==n+1){
		for(int i=1;i<=n;i++){
			cout<<a[i]<<" \n"[i==n];
		}
		return;
	}
	for(int i=1;i<=n;i++){
		if(vis[i])continue;
		vis[i]=1;//
		a[dep]=i;
		dfs(dep+1);
		vis[i]=0;//
	}

}
int main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
 	cin>>n;
 	dfs(1);
	return 0;
}

也可以使用库函数 next_permutaition()：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+5;
int main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
 	int n;cin>>n;
 	vector<int> a(n);
 	for(int i=1;i<=n;i++){
 		a[i-1]=i;
	 }
 	do{
 		for(int i=0;i<n;i++)cout<<a[i]<<" \n"[i==n-1];
	}while(next_permutation(a.begin(),a.end()));
	return 0;
}

2、取每位数的模

def isNmp:
	while(x):
		 t=x%10;
		 if 正确
		 	return true
		 x/=10;
return false

3、回文日期

1. int year = j % 10 * 1000 + (j / 10) * 100 + i % 10 * 10 + i / 10;

   • 这行代码是将给定的月份 i 和天数 j 转换为一个四位数的年份。类似于之前，j 被分成十位和个位，然后乘以相应的权重，而 i 也类似地处理，确保每个数字都在正确的位置上。最后，将它们加起来形成一个四位数的年份。

2. int sum = year * 10000 + i * 100 + j;

   • 这行代码是将年份、月份和日期合并成一个整数表示一个完整的日期。年份乘以 10000 是为了把它移到正确的位置，月份乘以 100 是为了把它移到正确的位置，最后把日期直接加到末尾即可。

#include<bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	// 1   2  3   4   5   6   7   8   9   10   11   12
	// 31     31  30  31  30  31  31  30  31   30   31
	// 判断2月是否是闰年 =>  return x%400==0 || (x%4==0 && x%100!=0)
	// 闰年 29天 ，平年 28天
	int y[]={0,31,29,31,30,31,30,31,31,30,31,30,31};
	int n,m;cin>>n>>m;
	int ans=0;
	for(int i=1;i<=12;i++){
		for(int j=1;j<=y[i];j++){
			int year=j%10*1000+(j/10)*100+i%10*10+i/10;
			int sum=year*10000+i*100+j;
			if(sum>m||sum<n)continue;
			else ans++;
		}
	}
	cout<<ans;
	return 0;
}