题目描述 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<cstdio> #include<iostream> 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 ",sum); return 0; }