/*
ID: lvxiaol3
LANG: C++
TASK: zerosum
*/
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
#include <cmath>
#include <sstream>
using namespace std;
int process(string ss)
{
string s;
for(int i=0;i< ss.size();i++) if(ss[i]!=' ') s+=ss[i];
int ret=0;
istringstream k;
k.str(s);
int a;
k>>a;
ret+=a;
char p;
while(k>>p)
{
k>>a;
if(p=='+') ret+=a;
if(p=='-') ret-=a;
}
return ret;
}
int main()
{
ifstream fin("zerosum.in");
ofstream fout("zerosum.out");
int N;
fin>>N;
vector<string> res;
for(int i=0;i<pow(3.0,N-1.0);i++)
{
int m=i;
string exp="1";
for(int j=2;j<=N;j++)
{
if(m%3==0){ exp+="+";exp+='0'+j;}
if(m%3==1){ exp+="-";exp+='0'+j;}
if(m%3==2){ exp+=" ";exp+= '0'+j;}
m/=3;
}
if(process(exp)==0) res.push_back(exp);
}
sort(res.begin(),res.end());
for(int i=0; i< res.size(); i++) fout<< res[i]<<endl;
return 0;
}
枚舉3進(jìn)制，或者dfs來(lái)獲得每一個(gè)字符串，然后單獨(dú)處理。
// 重新啟用這個(gè)blog，記錄一些做過(guò)的東西。。。