题目：将1, 2, 3, 4, 5, 6, 7, 8, 9 这九个数字，不改变顺序，用加减号连起来（允许减号出现在1的前面），使其结果等于100。

//将1, 2, 3, 4, 5, 6, 7, 8, 9 这九个数字，不改变顺序，
// 用加减号连起来（允许减号出现在1的前面），使其结果等于100。
// 请编程输出所有可能的情况，数字和符号之间不要有空格，如1+23-4+56+7+8+9＝100。
import javax.script.scriptEngine;
import javax.script.scriptEngineManager;
import javax.script.scriptException;
//另一种做法：dfs
class Solution {
    public static void possibleSum(int N) {
        //op中0表示-，1表示合并，2表示+
        int count=0;//统计等于100的表达式
        int op[] = new int[9];//9个数字中间（包括开头的-号）有9个填写符号的位置
        //后面8个位置有三种可能，开头有2种可能
        for (op[0] = 0; op[0] < 2; op[0]++)
            for (op[1] = 0; op[1] < 3; op[1]++)
                for (op[2] = 0; op[2] < 3; op[2]++)
                    for (op[3] = 0; op[3] < 3; op[3]++)
                        for (op[4] = 0; op[4] < 3; op[4]++)
                            for (op[5] = 0; op[5] < 3; op[5]++)
                                for (op[6] = 0; op[6] < 3; op[6]++)
                                    for (op[7] = 0; op[7] < 3; op[7]++)
                                        for (op[8] = 0; op[8] < 3; op[8]++) {
                                            if (AlgebraExpress(op) == N) {
                                            count++;
                                        }
                                    }
        System.out.println("Total : " + count);
    }

    public static int AlgebraExpress(int[] op) {
        //将表达式表示为字符串
        StringBuffer express = new StringBuffer() ;
        int re,count=0;
        String[] a = {"1","2","3","4","5","6","7","8","9"};
        if(op[0]==1){//如果开始为-
            express.append('-');//表达式追加-
        }
        for(int i=0,j=1;j<9;j++,i++){
            express.append(a[i]);//追加数字（类型是字符）
            if(op[j]==0){
                express.append('-');
            }
            else if(op[j]==2){
                express.append('+');
            }
            else
                continue;
        }
        express.append(a[8]);//追加最后一个数字
        //字符串表达式求值
        Integer re1 = expressSum(express);
        if (re1 != null) return re1;

        return 0;
    }

    private static Integer expressSum(StringBuffer express) {
        int re;
        //javascript可以直接求字符串形式的值，Java可以导包实现这一功能
        scriptEngineManager scriptEngineManager = new scriptEngineManager();
        scriptEngine scriptEngine = scriptEngineManager.getEngineByName("nashorn");
        String str = express.toString();
        try {
            String result = String.valueOf(scriptEngine.eval(str));
            //System.out.println(result);
            re=Integer.parseInt(result);
            if(re==100){
                System.out.println(express +"=100");
            }
            return re;
        } catch (scriptException e) {
            e.printStackTrace();
        }
        return null;
    }

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

参考资料：(15条消息) 1~9中间插入加号或减号使运算结果等于100_tao617的专栏-CSDN博客