等式变换
描述:    输入一个正整数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 online_judge;

public class Solution {
	static int count;
	//算法思想：每个空格有三种情况，不放入或者+或者-
	public void search(int[] result, int index,int target) {
		if (index == 8) {
			showResult(result,target);	
			return;
		} else {
			for (int i = 0; i < 3; i++) {
				result[index] = i;
				search(result, index + 1,target);
				result[index] = 0;
			}
		}
	}

	public static void showResult(int[] result,int target) {
		int sum = 0;
		String num = "";
		String exp = "";
		String[] source = { "1", "2", "3", "4", "5", "6", "7", "8", "9" };
		char oper = '+';
		num += source[0];
		exp += source[0];
		for (int i = 0; i < result.length; i++) {
			switch (result[i]) {
			case 0:
				num += source[i + 1];
				exp += source[i + 1];
				break;
			case 1:
				// 这里计算实际为遇到这个运算符前面部分表达式的值
				sum = caculate(num, sum, oper);
				oper = '+';
				//遇到运算符号清空
				num = "";
				num += source[i+1];
				exp+="+"+source[i+1];
				break;
			case 2:
				sum = caculate(num, sum, oper);
				oper = '-';
				num = "";
				num += source[i+1];
				exp+="-"+source[i+1];
				break;
			}
		}
		// 我们每次在碰到+或者-时进行计算，而计算是求得运算前面表达式的值，所以最后一个number 还没有计算进来。
		sum = caculate(num, sum, oper);
		if(sum == target){
			System.out.println(exp+" = "+target);
			count++;
		}
	}

	public static int caculate(String string,int sum,char op) {
		if(op == '+'){
			sum+= Integer.parseInt(string);
		}else {
			sum-= Integer.parseInt(string);
		}
		return sum;
	}

	public static void main(String[] args) {
		int [] res = new int[8];
		Solution s = new Solution();
		int target = 5;
		s.search(res, 0,target);
		System.out.println(count);
	}

}

 结果输出：

12-34+5-67+89 = 5
1+23+4-5+6-7-8-9 = 5
1+2+34-56+7+8+9 = 5
1+2+3+4-5+6-7-8+9 = 5
1+2+3+4-5-6+7+8-9 = 5
1+2+3-4+5+6-7+8-9 = 5
1+2-3+4+5+6+7-8-9 = 5
1+2-3-45+67-8-9 = 5
1+2-3-4+5-6-7+8+9 = 5
1+2-3-4-5+6+7-8+9 = 5
1-23+45+6-7-8-9 = 5
1-23+4+5-6+7+8+9 = 5
1-23-4-56+78+9 = 5
1-2+3+4-5-6-7+8+9 = 5
1-2+3-4+5-6+7-8+9 = 5
1-2+3-4-5+6+7+8-9 = 5
1-2-34-56+7+89 = 5
1-2-3+4+5+6-7-8+9 = 5
1-2-3+4+5-6+7+8-9 = 5
1-2-3-4-56+78-9 = 5
1-2-3-4-5-6+7+8+9 = 5
total types = 21