タイトル1498:検索式

タイトル1498:検索式
時間制限:1秒
メモリ制限:128メガ
特殊問題:いいえ
タイトルの説明:
現在、シーケンス123があります.N、ここで、Nは3〜15の間であり、このシーケンスからなる数学式の演算結果が0になるように、シーケンス間に+、−またはスペースを加えることが要求される.
 
入力:
入力には、複数のテストサンプルが含まれる場合があります.各テストケースについて、このシーケンスの長さを表す整数N(3<=N<=15)を入力します.
 
出力:
各テストケースに対応して、式の結果を0にするすべての組合せを出力し、複数の組合せがある場合、辞書順にソートして出力します.
 
サンプル入力:

3
6

サンプル出力:

1+2-3
1 2+3-4-5-6

ヒント:
 1_2+3-4-5-6は12+3-4-5-6に相当します(''はスペースを表します)
ソース:
マイクロ戦略2013年キャンパス招聘筆記試験問題
考え方:暴力、他の書き方を比較することができます.

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <map>
#include <vector>
#include <set>
#include <algorithm>
#include <vector>
#include <stack>
#include <math.h>
#include <stdlib.h>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long LL ;
const int size=18 ;
struct Me{
    int N ;
    int choose[size] ;
    Me(){} ;
    Me(int n):N(n){};
    LL ans(){
        // 1 ' '
        // 2 '+'
        // 3 '-'
         LL sum ,now ;
         int type=2 ;
         sum=0 ;
         now=1 ;
         choose[N]=2 ;
         for(int i=1;i<=N;i++){
            if(choose[i]==2||choose[i]==3){
                if(type==2)
                    sum+=now ;
                else
                    sum-=now ;
                type=choose[i] ;
                now=i+1 ;
            }
            else{
                if(i+1<=9)
                  now=now*10+i+1 ;
                else
                  now=now*100+i+1 ;
            }
         }
         return sum ;
    }
    void dfs(int id){
       if(id==N){
         if(ans()==0){
             printf("%d",1) ;
             for(int i=1;i<N;i++){
                if(choose[i]==1)
                    putchar(' ') ;
                else if(choose[i]==2)
                    putchar('+') ;
                else
                    putchar('-') ;
                printf("%d",i+1) ;
             }
             puts("") ;
          }
          return  ;
       }
       for(int i=1;i<=3;i++){
          choose[id]=i ;
          dfs(id+1) ;
       }
    }
};
int main(){
   int n ;
   while(scanf("%d",&n)!=EOF){
      Me me(n) ;
      me.dfs(1) ;
   }
   return 0 ;
}