这是一个回溯法的算法,可以用来寻找所有元素之和等于目标值的子集.
也就是:
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;
}
运行结果: