题目大意

给出序列1 2 3 … n，在序列的每个数字之间可以决定是否插入符号“+”、“-”。输出所有结果等于0的式子。

思路

简单枚举，用广搜枚举所有情况即可。

代码

/*
ID: lujunda1
LANG: C++
PROG: zerosum
*/
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<queue>
using namespace std;

struct state
//结构体state用于存储式子。 
{
	char str[20];
};

bool check(char* str,int n)
//判断式子str的结果是否为0。 
{
	int len=n*2-1;
	int sum=0,op=1,temp=1;
	//sum式子临时的结果。
	//op当前运算数的符号。
	//temp当前运算数的大小。 
	for(int i=1;i<len;i++)
		if(i%2)
		{
			if(str[i]==' ')
			{
				temp*=10;
				continue;
			}
			sum+=temp*op;
			op=str[i]=='+'?1:-1;
			temp=0;
		}
		else
			temp+=str[i]-'0';
	return sum+temp*op==0?true:false;
	//temp*op为str的结果。 
}

void bfs(int n)
{
	queue<state> q;
	state head;
	head.str[0]='1';
	head.str[1]='\0';
	q.push(head);
	int temp=1;
	while(++temp<=n)
	{
		int size=q.size();
		while(size--)
		{
			head=q.front();
			q.pop();
			head.str[temp*2-3]=' ';
			//按字典序，先' '，后'+'，最后'-'。 
			head.str[temp*2-2]='0'+temp;
			head.str[temp*2-1]='\0';
			q.push(head);
			head.str[temp*2-3]='+';
			q.push(head);
			head.str[temp*2-3]='-';
			q.push(head);
		}
	}
	while(q.size())
	{
		if(check(q.front().str,n))
			printf("%s\n",q.front().str);
		q.pop();
	}
}

int main()
{
	freopen("zerosum.in","r",stdin);
	freopen("zerosum.out","w",stdout);
	int n;
	scanf("%d",&n);
	bfs(n);
}