http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=2331

题目大意:(如题)
输入输出:(如题)
解题思路:
1.深搜。最大解空间为一棵深度为9的完全3叉树。
2.用sum表示之前所有数的和,num表示当前数,outs记录要输出的字符串,t记录层数。
3.每次按“ ”,“+”,“-”的顺序生成下一层的子节点。当t==n时,判断sum+num是否等于0,等于0则输出outs返回,否则直接返回。
核心代码:

if(t==n)
	{
		if(sum+num==0)
			cout<<outs<<endl;
		return;
	}
	if(num>=0)
		dfs(t+1,sum,outs+" "+char(t+1+48),num*10+t+1);
	else
		dfs(t+1,sum,outs+" "+char(t+1+48),num*10-t-1);
	dfs(t+1,sum+num,outs+"+"+char(t+1+48),t+1);
	dfs(t+1,sum+num,outs+"-"+char(t+1+48),-t-1);

发表评论

电子邮件地址不会被公开。

Post Navigation