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

Question

例如：1 + 2 + 34–5 + 67–8 + 9 = 100。

Answer 1

#include <stdio.h>
#include <math.h>
#define MAX 9
int temp[MAX];   //记录每次选的数的位数
int shuzu[MAX]={1,2,3,4,5,6,7,8,9};
int shu[MAX];   //记录每次选的数的数

void fun(int index,int num      //递归到第几层了
         )
{
    int i,j,z,   //第几个相加的数下标
        x,  //数分成的个数
        sum;
    if(index>=MAX)
    {       
        z=0;
        for(i=0;i<9;)
        {
            sum=0;
            for(j=0;j<temp[z];j++)
            {
                sum+=shuzu[i+j]*pow(10,temp[z]-1-j);    //每个数给算出来
            }       
            shu[z]=sum;
            z++;
            i+=j;
        }
        x=pow(2,num);       
        for(j=0;j<x;j++)
        {
            sum=0;
            for(i=0;i<num;i++)
            {
                if(i==0||j&(1<<i))
                {
                   sum+=shu[i];
                }
                else
                {
                   sum-=shu[i];
                }
            }
            /************输出结果*********/
            if(sum==100
                &&j&1)   //判断第一个符号（1之前的）是否为+ 
            {
              for(i=0;i<num;i++)
              {
                 if(i==0||j&(1<<i))
                 {
                    if(i==0)
                        printf("%3d",shu[i]);
                    else
                        printf(" +%3d",shu[i]);
                 }
                 else
                   printf(" -%3d",shu[i]);

              }
                printf("=%4d\n",sum);    //输出和
            }
        }       
    }
    else
    {   
        for(i=1;i<=3;i++)
        {   
            temp[num]=i;
            if(index+i>9) break;
            fun(index+i,num+1);
        }
    }


}

int main()
{
    fun(0,0);
    return 0;
}

Answer 2

递归求解.

private void computeInt(StringBuffer sb, int i, int res, int n, int sign){
    sb.append(i);
    n = n * 10 + i;
    if(i == 9){
        if(res + sign * n == 100)
            System.out.println(sb);
        deleteLast(sb);
        return;
    }

    // first case: no '+' or '-' appended
    computeInt(sb, i + 1, res, n, sign);

    if(getLast(sb) == '+' || getLast(sb) == '-')
        return;

    res += sign * n;

    // second case: '+' appended
    sb.append('+');
    computeInt(sb, i + 1, res, 0, 1);

    // third case: '-' appended
    replaceLast(sb, '-');
    computeInt(sb, i + 1, res, 0, -1);

    deleteLast(sb);
    deleteLast(sb);
}

@Test
public void compute(){
    computeInt(new StringBuffer(), 1, 0, 0, 1);
}

private char getLast(StringBuffer sb){
    return sb.charAt(sb.length() - 1);
}

private void deleteLast(StringBuffer sb){
    sb.deleteCharAt(sb.length() - 1);
}

private void replaceLast(StringBuffer sb, char c){
    sb.setCharAt(sb.length() - 1, c);
}