子集和问题 深搜回溯法

4.子集和问题

【问题描述】

        子集和问题的一个实例为<S，t>。其中，S={ x1，x2，…，xn}是一个正整数的集合，c是一个正整数。子集和问题判定是否存在S的一个子集S1，使得子集S1和等于c。

【编程任务】

        对于给定的正整数的集合S={ x1，x2，…，xn }和正整数c，编程计算S 的一个子集S1，使得子集S1和等于c。

【输入格式】

        由文件subsum.in提供输入数据。文件第1行有2个正整数n和c，n表示S的个数，c是子集和的目标值。接下来的1行中，有n个正整数，表示集合S中的元素。

【输出格式】

        程序运行结束时，将子集和问题的解输出到文件subsum.out中。当问题无解时，输出“No solution!”。

【输入样例】

5  10

2  2  6  5  4

【输出样例】

2  2  6

代码如下（带注释）：

 

#include<bits/stdc++.h>
using namespace std;
int n,c,s[210],d[110];     //d数组记录print时在s数组里用的数字的下标
bool b[110],can;           //b数组记录s数组中某个数字有没有用过
void dfs(int,int);
void print(int);
int main()
{
	cin>>n>>c;
	for(int i=1;i<=n;i++)
		cin>>s[i];
	d[0]=1;               //初始化
	dfs(1,0);
	if(!can)              //如果到最后都不行
		cout<<"No solution!";
	return 0;
}
void dfs(int k,int sum)
{
	if(can)
		return;          //找到了就一口气返回主程序
	if(sum==c)
	{
		print(k);        //找到了输出
		can=true;        //不用再找了
	}
	for(int i=d[k-1];i<=n;i++)  //防止重复，i从d[k]-1开始
		if(!b[i])        //如果新数字没用过
		{
			sum+=s[i];   //总和加上新的数
			b[i]=true;   //用过的不再用
			d[i]=i;      //记录
			dfs(k+1,sum);//递归
			sum-=s[i];   //回溯
			b[i]=false;  //回溯
		}
}
void print(int k)
{
	for(int i=1;i<k;i++)
		cout<<s[d[i]]<<" ";//输出解
	cout<<endl;
}