今天总算是碰到一道复杂题了。。。(我BT了?)
弄死我了,主要是排除重复情况,我想不通,最后参考了前人的代码,修改后AC了。。。
思路:通过递归,得出可能存在的解法,并记录,查找原记录,若存在相同则取消记录
#include <iostream>
#include <vector>
#include <string>
#include <stdlib.h>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int sum;
int sticknum;
int stick[20];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int mark[20];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int solution;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int sols[100][20]; //记录不重复的答案
int slen[100]; //记录第j组答案的长度
int solnum; //记录不重复的答案的数量
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void compute(int start,int cursum)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=start;i<sticknum;i++)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(mark[i]==0&&stick[i]<=cursum)
{
mark[i]=1;
int tmp=cursum-stick[i];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(tmp==0)
{
int tt=0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int j=0;j<sticknum;j++)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(mark[j]==1)
{
sols[solnum][tt++]=stick[j];
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(solution==0)
{ //如果是第一组答案,就直接记录
slen[solnum]=tt;
solution++;
solnum++;
mark[i]=0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
}else
{
bool test=false;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int k=0;k<solnum&&!test;k++)
{ //判断答案是否重复,如果重复就不对solnum加1,否则加1,
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(slen[k]==tt)
{ //先判断这两组组答案的长度是否相等,不等就直接判断下一组。
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int m=0;m<tt;m++)
{
if(sols[k][m]!=sols[solnum][m])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
break;
}
if(m==tt-1)test=true; //表示答案完全匹配,这一组答案就可以舍掉了
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(!test)
{ //如果答案与前面的都不重复,就对solution+1,solnum+1,
solution++;
slen[solnum]=tt;
solnum++;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
}else
{
compute(i+1,tmp);
}
mark[i]=0;
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
while(1)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
cin>>sum>>sticknum;
if(sum==0)break;
memset(stick,0,sizeof(stick));
memset(mark,0,sizeof(mark));
memset(sols,0,sizeof(sols));
memset(slen,0,sizeof(slen));
solution=0;
solnum=0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=0;i<sticknum;i++)
{
cin>>stick[i];
}
cout<<"Sums of "<<sum<<":"<<endl;
compute(0,sum);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(solution==0)
{
cout<<"NONE"<<endl;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
}else
{
for(int i=0;i<solnum;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
cout<<sols[i][0];
for(int j=1;j<slen[i];j++)
cout<<"+"<<sols[i][j];
cout<<endl;
}
}
}
}