基础算法之搜索与回溯算法C++

1、组合的输出

【题目描述】 排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且r≤n)，我们可以简单地将n个元素理解为自然数1，2，…，n，从中任取r个数。

现要求你用递归的方法输出所有组合。

例如n＝5，r＝3，所有组合为：

1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5

【输入】 一行两个自然数n、r(1<n<21，1≤r≤n)。

【输出】 所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。

【输入样例】 5 3 【输出样例】 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5

分析： 这题与一般的全排列题不同之处是：其中的元素按由小到大的顺序排列。这就意味着像 5 4 3 这样的排列是不行的，即后一个位置的元素要比前一个大

#include<iostream>
#include<iomanip>
using namespace std;
int n,r;
int a[300];
bool f[300]={0};
void print();
void search(int);
int main()
{
	cin>>n>>r;
	search(1);
	return 0;
}
void search(int k)
{
	if(k==r+1)//已经筛选出 1-r 位的数
	{
		print();
	}
	for(int i=1;i<=n;i++)//枚举 1-n 
	{
		if(!f[i]&&i>a[k-1])//该元素要比前一个大，没有使用过
		{
			a[k]=i;//把 该数放入k位
			f[i]=1;//标记该数用过
			search(k+1);//搜索下一位
			f[i]=0;//还原状态
		}
	}
}
void print()
{
	for(int i=1;i<=r;i++)
	{
		cout<<setw(3)<<a[i];
	}
	cout<<endl;
}

2、自然数的拆分

【题目描述】 任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。

当n=7共14种拆分方法：

7=1+1+1+1+1+1+1 7=1+1+1+1+1+2 7=1+1+1+1+3 7=1+1+1+2+2 7=1+1+1+4 7=1+1+2+3 7=1+1+5 7=1+2+2+2 7=1+2+4 7=1+3+3 7=1+6 7=2+2+3 7=2+5 7=3+4 total=14 【输入】 输入n。

【输出】 按字典序输出具体的方案。

【输入样例】 7 【输出样例】 7=1+1+1+1+1+1+1 7=1+1+1+1+1+2 7=1+1+1+1+3 7=1+1+1+2+2 7=1+1+1+4 7=1+1+2+3 7=1+1+5 7=1+2+2+2 7=1+2+4 7=1+3+3 7=1+6 7=2+2+3 7=2+5 7=3+4

#include<iostream>
#include<iomanip>
#include<cstring>
using namespace std;
int a[10000]={1};
int n;
void print(int);
void search(int,int);
int main()
{
	cin>>n;
	search(n,1);
	return 0;
}
void search(int s,int t)
{
	for(int i=a[t-1];i<=s;i++)//当前数要大于等于前一位数，所以每次从前一位数开始枚举，要小于等于当前未拆分的
	{
		if(i<n)//i要小于n
		{
			a[t]=i;
			s-=i;
			if(s==0)print(t);//剩余未拆分的==0，说明一种方案完成
			else search(s,t+1);//否则继续拆分
			s+=i;//还原状态
		}
	}
}
void print(int t)
{
	cout<<n<<"=";
	for(int i=1;i<=t-1;i++)
	{
		cout<<a[i]<<"+";
	}
	cout<<a[t]<<endl;
}