1983 等式问题

 

 时间限制: 1 s

 空间限制: 64000 KB

 题目等级 : 白银 Silver

 查看运行结果

 

 

题目描述 

Description

有一个未完成的等式：1 2 3 4 5 6 7 8 9=N 空格（1前面没有空格）内可以填入+,-,也可以不填。 编程找出输入某个整数 N 后使等式成立的所有方案的总数。保证有解。

输入描述 

Input Description

输入一个数N。

输出描述 

Output Description

输出一个数。所有的方案数。

样例输入 

Sample Input

108

样例输出 

Sample Output

15

数据范围及提示 

Data Size & Hint

 

分类标签 Tags 

 

 

 

水！

#include
          
           #include
           
            using namespace std;    int n,sum;void dfs(int k,int t){    if(t==n&&k>9){        sum++;return ;    }    int tmp=0;    for(int i=k;i<=9;i++){        tmp=tmp*10+i;        dfs(i+1,t+tmp);        if(k!=1)           dfs(i+1,t-tmp);    }}int main(){    scanf("%d",&n);    dfs(1,0);    printf("%d\n",sum);    return 0;}