1~9中间插入加号或减号使运算结果等于100

题目：编写一个在1，2，…，9（顺序不能变）数字之间插入+或-或什么都不插入，使得计算结果总是 100 的程序，并输出所有的可能性。

算法分析

本题算法不算太难，但是编码相对麻烦一些，某一些实现方式分支比较多，也不容易调试。

首看分析一下计算复杂度。1到9之间共有8个位置，每个位置有'+'、'-'和''（空字符）在三种选择，一共是3的8次方（6561种选择），所以即使是暴力解法，时间复杂度最多是O（6561），完全没有问题。再看看空间复杂度，我们先生成每种解法的字符串形式算术表达式，例如，"1+2+3+4+5-6+7+8+9"，每个表达式应远小于1k，6561种表达式应该小于6M，内存也够用。

难点在于编码上的处理：

1、首先，如何暴力求解，分别对8个位置上的符号进行遍历，需要8层循环，写起来可能比较麻烦。而且如果题目稍作修改，提升一下难度，数字序列的长度不固定， 是个变量，从1到n，那这种就没有办法写了。所以即使是暴力求解，也需要一些小技巧，为简化编码和调试，最好使用递归。

2、其次，是数据存放形式的选择。是分别使用两个数组存放数字和运算符？还是使用字符串存放表达式，然后再解析？由于最终要输出或者存储所有表达式，第二种方式可能相对好些，避免了将最终结果转化成字符串的过程。而且后面可以看到，字符串存储数据更便于递归。

3、非递归写法，需要处理表达式的求值。这块其实是个简单的计算器，或者说是个最简单的编译器。可能会仅处理'+'、'-'，或者处理'+'、'-'、''（合并）三种。采用字符串形式可以避免处理两数合并的情况，这样剩下的'+'和'-'运算优先级相同，编码进一步简化。

编程语言的选择：

如果可以选择，python是最佳选择。因为相比于java、C、C++、C#等语言，python处理字符串非常灵活、简便。此外，python内置库函数eval( )，功能正好是实现字符串表达式的求值。而由于python处理字符串方面的优势，暴力或递归（其实也是暴力方法）生成全部可能的表达式也很方便。javascript也有内置eval( )函数，处理本题也比较方便。

具体代码

首先来看一下相对简洁的纯递归解法，java实现：

第一种，基于字符串实现：

import java.util.ArrayList;
import java.util.List;

class Solution {
	public static List<String> PossibleSum(String numSeq, int n, int N) {
		List<String> result = new ArrayList<String>();
		// 因为有""连接两个数字，所以以1到9为例，最外层需要考虑123456789， 23456789， 3456789，..., 9共9种情况
		for (int i = 0, lastVal = 0; i < n; i++) {
			lastVal = Integer.parseInt(numSeq.substring(i, n));
			// 范围内没有运算符号，全是数字直接相连, 作为退出条件
			if (i == 0) {
				if (lastVal == N)	result.add("" + lastVal);
				continue; // 此时没有下一层递归
			}
			// 以下开始递归运算
			// -
			if (PossibleSum(numSeq, i, N - lastVal).size() != 0)
				for (String s : PossibleSum(numSeq, i, N - lastVal))
					result.add(s + "+" + lastVal);
			// +
			if (PossibleSum(numSeq, i, N + lastVal).size() != 0)
				for (String s : PossibleSum(numSeq, i, N + lastVal))
					result.add(s + "-" + lastVal);
		}
		return result;
	}

	public static void main(String[] args) {
		List<String> resultList = PossibleSum("123456789", 9, 100);
		for (String s : resultList) {
			System.out.println(s + "=100");
		}
		System.out.println("Total : " + resultList.size());	
	}
}

其实当最后一个数字很大，例如，456789，前面1、2、3三个数字怎么组合都不可能行于100+456789或100-456789，于是可以利用这种特性进行粗略的剪枝。

进一步优化，增加剪枝，去掉不必要的递归调用：

import java.util.ArrayList;
import java.util.List;

class Solution {
	public static List<String> PossibleSum(String numSeq, int n, int N) {
		List<String> result = new ArrayList<String>();
		int max, min;
		// 因为有""连接两个数字，所以以1到9为例，最外层需要考虑123456789， 23456789， 3456789，..., 9共9种情况
		for (int i = 0, lastVal = 0; i < n; i++) {
			lastVal = Integer.parseInt(numSeq.substring(i, n));
			// 范围内没有运算符号，全是数字直接相连, 作为退出条件
			if (i == 0) {
				if (lastVal == N)
					result.add("" + lastVal);
				continue; // 此时没有下一层递归
			}
			// 为剪枝作准备，目标值超过当子递归范围时，不再进行递归，剪枝可选，不是必须的，而且要注意逻辑的正确性
			if (i > 1) {
				max = Integer.parseInt(numSeq.substring(0, i));
				min = Integer.parseInt(numSeq.substring(0, 1)) - Integer.parseInt(numSeq.substring(1, i));
			} else {
				max = min = Integer.parseInt(numSeq.substring(0, 1));
			}
			// 以下开始递归运算
			// -
			if (N - lastVal <= max && N - lastVal >= min && PossibleSum(numSeq, i, N - lastVal).size() != 0)
				for (String s : PossibleSum(numSeq, i, N - lastVal))
					result.add(s + "+" + lastVal);
			// +
			if (N + lastVal <= max && N + lastVal >= min && PossibleSum(numSeq, i, N + lastVal).size() != 0)
				for (String s : PossibleSum(numSeq, i, N + lastVal))
					result.add(s + "-" + lastVal);
		}
		return result;
	}

	public static void main(String[] args) {
		List<String> resultList = PossibleSum("123456789", 9, 100);
		for (String s : resultList) {
			System.out.println(s + "=100");
		}
		System.out.println("Total : " + resultList.size());	
	}
}

基于数字的纯递归实现，缺点是递归过程数字处理逻辑相对复杂，而且只能处理1到n(n<=9)的增序或降序排列。而上述基于字符串的处理方法可以处理任意数字顺序的序列。但基于数字的处理也有好处，相对节省内存，不需要存储长为3的n次方的表达式列表。

import java.util.ArrayList;
import java.util.List;

class Solution {
	public static List<String> PossibleSum(int n, int N) {
		List<String> result = new ArrayList<String>();
		int a = 0;
		for (int i = 0; i < n; i++) {
			// a代表表达式的最后一个数字，a的迭代处理是难点
			a = (int) (a + (n - i) * Math.pow(10, i));
			// System.out.println("i is: "+i+"|a is: "+a);
			// 范围内没有运算符号，全是数字直接相连, 作为退出条件
			if (i == n - 1 && a == N) {
				result.add("" + a);
			}
			// -
			if (PossibleSum(n - i - 1, N - a).size() != 0)
				for (String s : PossibleSum(n - i - 1, N - a))
					result.add(s + "+" + a);
			// +
			if (PossibleSum(n - i - 1, N + a).size() != 0)
				for (String s : PossibleSum(n - i - 1, N + a))
					result.add(s + "-" + a);
		}
		return result;
	}

	public static void main(String[] args) {
		List<String> resultList = PossibleSum(9, 100);
		for (String s : resultList) {
			System.out.println(s + "=100");
		}
		System.out.println("Total : " + resultList.size());
	}
}

递归实现有一点需要注意，最好是针对算术表达式“1+2-3...9"从后往前递归，即，前n位的算述表达式值'+'或'-'后面n+1位到9合并后的值等于100（目标值）。从前往后递归的话，由于运算优先级问题，会很难处理。

接下来看看基于递归的暴力解法，即先由递归生成所有可能的算术表达式，然后对每个算术表达式求值，保留值等于目标值的表达式作为结果。

首先来看一下最简单的python实现，代码简洁程度不亚于上述的递归写法

import time
import re


class PSum(object):

    def all_possible_sum(self, n, s):
        plist = self.all_strings(n)
        result = []
        for command in plist:
            if eval(command) == s:
                result.append(command + '=' + str(s))
        return result

    def all_strings(self, n):
        if n == 1:
            return ['1']
        result = []
        for s in self.all_strings(n - 1):
            result.append(s + str(n))
            result.append(s + "+" + str(n))
            result.append(s + '-' + str(n))
        return result


if __name__ == '__main__':
    p = PSum()
    start_time = time.time()
    res = p.all_possible_sum(9, 100)
    for i in res:
        print(i)
    end_time = time.time()
    print('Total counts: ', len(res))
    print('time cost: ', end_time - start_time)

javascript版本类似，都是基于eval( )函数

function gs(n) {
    var result = new Array()
    if (n == 1) return ['1']
    x = gs(n - 1)
    for (i in x) {
        result.push(x[i] + n)
        result.push(x[i] + '+' + n)
        result.push(x[i] + '-' + n)
    }
    return result
}

function allPossibleSum(n){
    exprs = gs(9)
    c = 0
    for(i in exprs){
        if(eval(exprs[i])==100){
            console.log(exprs[i]+"=100")
            c = c + 1
        }
    }
    console.log("Total : " + c)
}

allPossibleSum(100)

// console.log(gs(3))

同样算法的java实现，需要自己编写计算表达式的函数。

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

class Solution {
	// 还有一种就是字符串暴力解法，类似于Python编码，先生成字符串式子
	public static List<String> PossibleSum(int N) {
		List<String> result = new ArrayList<String>();
		List<String> list = allPossibleString("123456789", 0);
		for (String s : list) {
			if (computeValue(s) == N)
				result.add(s);
		}
		return result;
	}

	// 生成所有可能的字符串
	public static List<String> allPossibleString(String s, int start) {
		List<String> result = new ArrayList<String>();
		if (start == s.length() - 1) {
			result.add(s.substring(start));
			return result;
		}
		for (String xs : allPossibleString(s, start + 1)) {
			result.add(s.substring(start, start + 1) + xs);
			result.add(s.substring(start, start + 1) + "-" + xs);
			result.add(s.substring(start, start + 1) + "+" + xs);
		}
		return result;
	}
	
	// 需要自己编写表达式计算函数，也可以使用
	public static int computeValue(String s) {
		// 一次遍历，或者正则表达式直接搜索'+'、'-'
//		int start = 0, x1, x2;
//		Deque<Integer> operandStack = new LinkedList<Integer>();
//		Deque<Character> symbolStack = new LinkedList<Character>();
//		for (int i = 1; i < s.length(); i++) {
//			if (!Character.isDigit(s.charAt(i))) {
//				if (symbolStack.isEmpty()) {
//					operandStack.push(Integer.parseInt(s.substring(start, i)));
//				} else {
//					x1 = operandStack.pop();
//					x2 = Integer.parseInt(s.substring(start, i));
//					operandStack.push(symbolStack.pop() == '+' ? x1 + x2 : x1 - x2);
//				}
//				symbolStack.push(s.charAt(i));
//				start = i + 1;
//			}
//		}
//		x2 = Integer.parseInt(s.substring(start, s.length()));
//		return operandStack.isEmpty() ? x2 : operandStack.pop() + (symbolStack.pop() == '+' ? x2 : (0 - x2));
		// 正则表达式方式，但java的正则表达式比较弱
		Deque<Integer> operandStack = new LinkedList<Integer>();
		Deque<Character> symbolStack = new LinkedList<Character>();
		Pattern p = Pattern.compile("[1-9]+"); // 也可以找数字，逻辑上都差不多
		Matcher matcher = p.matcher(s);
		while (matcher.find()) {
			if (symbolStack.isEmpty()) {
				operandStack.push(Integer.parseInt(matcher.group()));
			} else { // 只剩下加、减操作了
				int x = operandStack.pop();
				int y = Integer.parseInt(matcher.group());
				operandStack.push(symbolStack.pop() == '+' ? x + y : x - y);
			}
			// end端是开区间，正好处于符号位的下标
			if (matcher.end() < s.length())
				symbolStack.push(s.charAt(matcher.end()));
		}
		return operandStack.pop();
	}
	public static void main(String[] args) {
		for(String s : PossibleSum(100)) {
			System.out.println(s+"==100");
		}
		System.out.println("Total is: "+PossibleSum(100).size());
		
			
	}
}

 或者强行使用已经要被移除的ScriptEngine，如下图：

最后一种方式，就是使用两个数组分别存储数字和运算符。为方便迭代，使用数字0、1、2代表'+'、'-'和''（空）三种运行符，计算出结果如果满足条件，再转换成数字。这种方法也相对省内存，但缺点前面已经说了，不灵活，数字数组长度必须固定。

class Solution {
	public static void possibleSum(int N) {
		// 缺点是如果数字序列长度不固定，就没有办法写了，优点是思路简单
		int count = 0;
		int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
		int opers[] = new int[8];
		for (opers[0] = 0; opers[0] < 3; opers[0]++)
			for (opers[1] = 0; opers[1] < 3; opers[1]++)
				for (opers[2] = 0; opers[2] < 3; opers[2]++)
					for (opers[3] = 0; opers[3] < 3; opers[3]++)
						for (opers[4] = 0; opers[4] < 3; opers[4]++)
							for (opers[5] = 0; opers[5] < 3; opers[5]++)
								for (opers[6] = 0; opers[6] < 3; opers[6]++)
									for (opers[7] = 0; opers[7] < 3; opers[7]++) {
										if (sum(a, opers) == N) {
											count++;
											printSum(a, opers);
											System.out.println("=" + N);
										}
									}
		System.out.println("Total : " + count);
	}

	public static void printSum(int a[], int oper[]) {
		int i = 0;
		for (i = 0; i < oper.length; i++) {
			System.out.print(a[i]);
			switch (oper[i]) {
			case 0:
				System.out.print("");
				break;
			case 1:
				System.out.print("+");
				break;
			case 2:
				System.out.print("-");
				break;
			default:
				System.out.print("!");
			}
		}
		System.out.print(a[i]);
	}

	public static int sum(int[] a, int[] opers) {
		  // 思路简单，就是边界比较多，编码繁琐还容易错，调试不太容易
		  /********************************************
		    * 加、减还有合并三种运算的简易计算器，由于涉及合并，而合并运算优先级高于'+'或'-'，
		    * 所以处理当前运算符的时候，要考虑前一个运算符，preOper变量存储前一个运算符
		   *******************************************/
		  // 暂不考虑数据数组为空的无意义的边界情况
//			if (a.length == 1)
//				return a[0];
//			//
//			int x1 = a[0], x2 = a[1], preOper = opers[0];
//			for (int i = 1, j = 1; i < opers.length; i++) { // i用作opers下标，j用作是a的下标
//				if (opers[i] == 0) { // 合并拥有最高优先级。即使前一个运算符也是合并，先做本次合并也不影响结果。
//					x2 = x2 * 10 + a[++j]; // 这里假设a和opers两个数组数据量严格对应，即a.length = opers.length + 1
//				} else {
//					if (preOper == 0)
//						x1 = x1 * 10 + x2;
//					else
//						x1 = preOper == 1 ? x1 + x2 : x1 - x2;
//					x2 = a[++j];
//					preOper = opers[i];
//				}
//				if (i == opers.length - 1) { // 最后一个运算符
//					if (preOper == 0)
//						x1 = x1 * 10 + x2;
//					else
//						x1 = preOper == 1 ? x1 + x2 : x1 - x2;
//				}
//			}
//			return x1;
		  
			if (a.length <= 0 || a.length != opers.length + 1)
				return (Integer) null;
			if (a.length == 1)
				return a[0];
			int x = a[0], y = a[1], oper = -1;
			for (int i = 0, j = 1; i < opers.length; i++) {
				if (oper == -1) { // 代表没有出现过'+'或'-'
					if (opers[i] == 0) {
						x = x * 10 + y;
						if (++j < a.length)
							y = a[j]; // 下标安全校验，如果都去掉，代码还是很简洁的
						else
							break;
					} else
						oper = opers[i];
				} else {
					if (opers[i] == 0) {
						if (++j < a.length)
							y = y * 10 + a[j];
						else
							break;
					} else {
						x = oper == 1 ? x + y : x - y;
						if (++j < a.length)
							y = a[j];
						else
							break;
						oper = opers[i];
					}
				}
			}
			if (oper != -1) // 代表至少出现过一次'+'或'-'
				x = oper == 1 ? x + y : x - y;
			return x;
		 }

	public static void main(String[] args) {
		possibleSum(100);		
	}
}

上述的解答方案各有利弊，递归方式代码简单，但是调试时需要进入子递归，层数多了会有点乱。非递归方式编码相对复杂，逻辑分支也比较多，也容易出错。

本文地址：https://blog.csdn.net/tao617/article/details/107547933