回溯法寻找元素之和等于目标值的子集

这是一个回溯法的算法,可以用来寻找所有元素之和等于目标值的子集.

整个算法中最重要的是:在递归之后"恢复现场"

也就是:

t[cnt]=0;
cnt--;

完整代码(注释部分打印信息可以用来辅助理解递归过程)：

#include<iostream>
#include<cstring>
using namespace std;
const int N=1010;
int x[N],t[N];
int cnt,n,goal;
void BACKTRACKREC(int k)
{	
	for(int i=1;i<=n;i++)
	{	
		t[cnt++]=x[i];
		int total=0;
		for(int i=0;i<cnt;i++)
			total+=t[i];
			
//		printf("BACKTRACKREC(%d)递归前,i=%d,total=%d\n",k,i,total);
//		printf("t数组:\n");
//		for(int j=0;j<cnt;j++)
//			printf("%d ",t[j]);
//		printf("\n");
		
		if(total<goal)
		{	
			BACKTRACKREC(k+1);
			t[cnt]=0;
			cnt--;
		}
		else if(total>goal)
		{
			t[cnt]=0;
			cnt--;
		}
		if(total==goal)
		{
			for(int i=0;i<cnt;i++)
				cout<<t[i]<<' ';
			cout<<endl;
			t[cnt]=0;
			cnt--;
		}
		
//		printf("BACKTRACKREC(%d)递归后,i=%d,total=%d\n",k,i,total);
//		printf("t数组:\n");
//		for(int j=0;j<cnt;j++)
//			printf("%d ",t[j]);
//		printf("\n");
	}
}
int main()
{
	cin>>n>>goal;
	
	for(int i=1;i<=n;i++)
		scanf("%d",&x[i]);
	
	BACKTRACKREC(1);
	
	return 0;
}

运行结果：