2015届华为校园招聘机试题(2)

第三题：等式变换
输入一个正整数X，在下面的等式左边的数字之间添加+号或者-号，使得等式成立。
1 2 3 4 5 6 7 8 9 = X
比如：
12-34+5-67+89 = 5
1+23+4-5+6-7-8-9 = 5
请编写程序，统计满足输入整数的所有整数个数。
输入：      正整数，等式右边的数字
输出：      使该等式成立的个数
样例输入：5
样例输出：21

#include<iostream>
#include<cstdio>
using namespace std;

int ops[21];
const char sym[3] = {'+' , '-' , ' '};
int result , num;

void dfs(int layer, int currentResult, int lastOp, int lastSum)
{
 lastSum *= (layer > 9) ? 100 : 10;
 lastSum += layer;
 if(layer == 9)
 {
  currentResult += (lastOp) ? (-1 * lastSum) : lastSum;
  if(currentResult == result)
  {
   ++num;
   printf("1");
   for(int i = 2 ; i <= 9 ; ++i)
   {
    if(sym[ops[i-1]] != ' ')
     printf(" %c ", sym[ops[i-1]]);
    printf("%d", i);
   }
   printf(" = %d\n" , result);
  }
  return;
 }
 ops[layer] = 2;
 dfs(layer + 1 , currentResult , lastOp , lastSum);  //Continue
 currentResult += (lastOp)? (-1 * lastSum) : lastSum;
 ops[layer] = 0;
 dfs(layer + 1 , currentResult , 0 , 0);  //Plus
 ops[layer] = 1;
 dfs(layer + 1 , currentResult , 1 , 0);  //Minus
}

int main(void)
{
 while(scanf("%d", &result) != EOF)
 {
  num = 0;
  dfs(1 , 0 , 0 , 0);
  printf("%d\n" , num);
 }
 return 0;
}