1983 等式问题

题目描述 Description

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

输入描述 Input Description

输入一个数N。

输出描述 Output Description

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

样例输入 Sample Input

108

样例输出 Sample Output

15

#include<iostream> #include<cmath> using namespace std; int n,m=0; void search(int,int); int main() { cin>>n; for (int i=1;i<=9;++i) { int s=0; for(int j=1;j<=i;++j) s=s*10+j; search(i+1,s); } cout<<m; return 0; } void search(int x,int y) { if(x>9) {if(y==n) m++; return ; } for(int i=x;i<=9;i++) { int s=0; for(int j=x;j<=i;j++) s=s*10+j; search(i+1,y+s); search(i+1,y-s); } }

一个搜索问题。