输入一个正整数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

package huawei;import java.util.*;/** * 从数的角度看 * @author Administrator */public class Equation1 {		private static List
    
     
      > list = new ArrayList<>();		private static List
      
       
        > op_list = new ArrayList<>();	//如若元素不是有序的则需用到	private static int [] ele = {1,2,3,4,5,6,7,8,9};		private static int result = 5;		public static void main(String[] args) {		// TODO Auto-generated method stub		getResult(result);	}		public static int getResult(int c) {		fun(9);		int count = 0;		System.out.println(op_list.size());		for(int k=0; k
        
          l = op_list.get(i);				int sum = 0;				for(int j=0; j
         
          0){ count++; System.out.println(l.toString()); } } } System.out.println("count:"+count); return count; } //所有数字有可能的组合 public static int fun(int c) { if(c==1){ List gen = new ArrayList(); gen.add(1); list.add(gen); return 1; } int r = 0; r = r + 2*fun(c-1); int k = list.size(); for(int i=0; i
         
        
       
      
     
    

package huawei;import java.util.ArrayList;import java.util.List;/** * 从符号的角度看 * @author Administrator * */public class Equation2 {		private static List
    
     
      > list = new ArrayList<>();		private static List
      
        op_list = new ArrayList<>();	//如若元素不是有序的则需用到	private static int [] ele = {1,2,3,4,5,6,7,8,9};		private static char [] op = {'+','-',' '};	public static void main(String[] args) {		// TODO Auto-generated method stub		getResult(5);	}		public static int getResult(int c) {		int count = 0;		int r = fun_op(7);		System.out.println("r:"+r);				for(int i=0; i
      
     
    

转载的解法

#include
    
       #include
     
        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;  }
     
    

这种代码最简单，关键是注意

currentResult += (lastOp)? (-1 * lastSum) : lastSum;  、

的位置，这是直接加上或者减去后面一个数。因为不能确定后面一个数是单独的数，还是作为下一个数的前一位，故要将“前一位”这种情况放到这句代码的前面递归，首先解决这种情况。