深度优先搜索
小木棍
int cnt=0;
bool dfs(int len,int now,int used,int last)//枚举的长度 现在拼的长度 使用的棍棒数量
{
if((used==n)&&(now==len)) return 1;
if(now==len)
{
int fail=0;
for(rint i=1;i<=n;i++)
{
if(vis[i]) continue; if(a[i]==fail) continue;
vis[i]=1;
if( dfs(len,a[i],used+1,i+1) ) return 1;//这一根总是要用的 这次失败下次也要失败( 等效状态下的失败)
vis[i]=0; fail=a[i];
return false;
}
}
else
{
int fail=0;
for(rint i=last;i<=n;i++)
{
if(vis[i]) continue; if(a[i]==fail) continue;
if(now+a[i]<=len)
{
vis[i]=1;
if( dfs(len,now+a[i],used+1,i+1) ) return 1;
vis[i]=0; fail=a[i];
if(now==0||now+a[i]==len) return 0;
}
}
}
return 0;
}
以为把所有的now=0 的情况都划到了now==len的情况 但是实际上你最开始是按照0开始搜索的 导致最初的那个状态没有被剪枝
准确的来说 应该是剪枝没有剪彻底 分类讨论的时候漏了情况
搜索的时候不是按照第一根来搜的 是从第0根开始搜索的