一个有趣的算法题。各位能不能给点思路。有代码更好，最好是java的代码。谢谢！

Question

  匪警请拨110,即使手机欠费也可拨通！    为了保障社会秩序，保护人民群众生命财产安全，警察叔叔需要与罪犯斗智斗勇，因而需要经常性地进行体力训练和智力训练！    某批警察叔叔正在进行智力训练：    1 2 3 4 5 6 7 8 9 = 110;    请看上边的算式，为了使等式成立，需要在数字间填入加号或者减号（可以不填，但不能填入其它符号）。之间没有填入符号的数字组合成一个数，例如：12+34+56+7-8+9 就是一种合格的填法；123+4+5+67-89 是另一个可能的答案。    请你利用计算机的优势，帮助警察叔叔快速找到所有答案。    每个答案占一行。形如：12+34+56+7-8+9
123+4+5+67-89
......

Answer 1

public class Test{
    public static void main(String args[]){
        String str="123456789";
        char[] chars = str.toCharArray();
        int[] array = new int[8];
        StringBuffer sb = new StringBuffer();        while(array[0]<3){
            sb.append(chars[0]);
            for(int k=0;k<chars.length-1;k++){
                if(array[k]==1){
                    sb.append("+");
                }
                else if(array[k]==2){
                    sb.append("-");
                }
                sb.append(chars[k+1]);
            }
            if(parse(sb.toString())){
                System.out.println(sb.toString());
            }
            sb.setLength(0);
            
            array[7]++;
            for(int i=7;i>0;i--){
                if(array[i]==3){
                    array[i]=0;
                    array[i-1]++;
                }
            }
            
        }
    }
    private static boolean parse(String str) {
        String[] str1 = str.split("[\\+]|[-]");
        String str2 = str.replaceAll("\\d*","");
        int sum = 0;
        sum = Integer.parseInt(str1[0]);
        for(int i=0;i<str1.length-1;i++){
            switch(str2.charAt(i)){
            case '+':
                sum+=Integer.parseInt(str1[i+1]);
                break;
            case '-':
                sum -=Integer.parseInt(str1[i+1]);
                break;
            }
        }
        if(sum==110){
            return true;
        }
        return false;
    }
}

Answer 2

这个while()循环没看大懂。能否具体解释下思路。为什么要那样添加+号-号，array数组的作用了。我水平不高啦。能否把程序的思路描述的更清楚些。谢谢啦

Answer 3

while语句遍历用的00000000相当于3进制，开始00000001，初始位没循环一次+1，当到3是，重置0位，下一位+1，其实就是3进制遍历的过程。然后0代表没有，1代表"+",2代表"-"。接着到了parse方法，我没考虑效率，先把符号插进去，在通过符号位把数据分裂出来，当然我没怎么考虑效率，只是为了自己方便一点写代码。其实有了那个数组就能分离数据了。接着计算表达式的值是不是110.

Answer 4

今天刚好做了一下这道题：
import java.util.ArrayList;
import java.util.List;public class Funny_equation {

List<String> list = new ArrayList<String>();
public void buildString(String str,int index) {
String s = str;
if(s.charAt(index)=='9'){
if(equation(s)) 
System.out.println(s);
return;
}else {
String s1 = s.substring(0,index+1)+"+"+s.substring(index+1,s.length());
buildString(s1,index+2);
String s2 = s.substring(0,index+1)+"-"+s.substring(index+1,s.length());
buildString(s2,index+2);
String s3 = s.substring(0,index+1)+""+s.substring(index+1,s.length());
buildString(s3,index+1);
}
}

public boolean equation(String s) {
String[] array = s.split("\\+");
int result = 0;
for(String e:array){

if(e.contains("-")) {
String[] temp = e.split("\\-");
result+=Integer.parseInt(temp[0]);
for(int i=1;i<temp.length;i++)
result-=Integer.parseInt(temp[i]);
}else{
result+=Integer.parseInt(e);
}
}
if(result==110) return true;
return false;
}

public static void main(String[] args) {
String  raw = "123456789";
Funny_equation test = new Funny_equation();
test.buildString(raw, 0);
}}