例如:1 + 2 + 34–5 + 67–8 + 9 = 100。
#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;
}
递归求解.
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);
}