小木棍

深度优先搜索

小木棍

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根开始搜索的