Question

编写程序求：给出一个整数n，一个数组{a1,a2,...,an}，将n表示成数组中若干项的和，写出所有的可能。

例如：n=10，数组为{1,8,4,3，5,2}，所有的可能为{1,4,3,2}，{1,4,5}，{8,2}，{3,5,2}。

Answer 1

递归就可以解决，给你写个递归式吧；调用方法如下
int a[6]={1,8,4,3,5,2};
int chose[6]={-1,-1,-1,-1,-1,-1};
decompose( a,5,0,10,chose,0);

void print( int *chose , int n ){
for( int i = 0 ; i < n ; ++i )
printf("%d\t",chose[i]);
printf("\n");
}
//参数分别是，背包数组，数组最大下标，当前选到的第k个元素，要求解的和，已选的结果，已选结果的下标
void decompose( int *array , int max , int k , int subn , int *chose , int c ){
if( subn < 0 )
return ;
if( !subn ){
print( chose , c );
}
for( int i = k ; i <= max ; ++i ){
chose[c] = array[i];
decompose( array , max , i+1 , subn-array[i] , chose , c+1 );
chose[c] = -1;
}
}

追问

我想知道的是输入一个数据n，数组也很大，用递归也行吗?

追答

那就比较慢了。这算法是n!的，我在给你一个思路吧，对于这种的更快。先对数组排序，然后再使用回溯法，求解的过程中剪枝会很快。

追问

能用回溯法写一下吗？

追答

下面是主要核心程序，给出了调用方式。主函数中调用了自己写的几个函数，快速排序，数组创建，以及输出数组函数，不影响阅读。去掉之后换成自己的就可以了，运行没问题。
int d[]={2,3,4,5,6,7,8,9,10};
GetAllTheCombination( d, 8,12);

//要选的数组，数组最大下标，要求的和m
void GetAllTheCombination( int *array , int n , int m ){
QuickSort( array , 0 , n );
print_array(array,n+1);
int sub = m;
int *chose_array = CreateArray(n);
int i = 0, chose = 0, count = 0;
//i是选择当前已选数的个数-1，chose是array当前中当前要选的数的下标，count记录总的组合法个数
while( i >= 0 ){
if( sub > 0 ){//当前剩余和大于0
if( sub > array[chose] ){//剩余和大于当前选的数
if( chose == n ){//选到了最后一个数
if( i <= 0 )//数组只有一个数，长度为一的话
break;
sub += array[ chose_array[i - 1] ];
chose = chose_array[i - 1] + 1;
--i;
}else{//加入选数，并计算出剩余的数，下一个要选的数，以及记录下一个数的位置
sub -= array[chose];
chose_array[i] = chose;
++chose;
++i;
}
}else if( sub == array[chose] ){//刚好得到了一种选法，并输出
chose_array[i] = chose;
//if( i == 5 ){
printf("array is:\n");
for( int k = 0 ; k <= i ; ++k )
printf("%d\t",array[ chose_array[k] ] );
printf("\n");
++count;
//}
if( i <= 0 )//第一个数刚好就满足，其他的数不用考虑，因为都大于第一个数
break;
sub += array[ chose_array[i - 1] ];//找下一种选法
chose = chose_array[i - 1] + 1;
--i;
}else{//剩余的数小于当前的数，退一步
if( i <= 0 )
break ;
sub += array[ chose_array[i - 1] ];
chose = chose_array[i - 1] + 1;
--i;
}
}else{//剩余的数小于0，退一步
if( i <= 0 )
break ;
sub += array[ chose_array[i - 1] ];
chose = chose_array[i - 1] + 1;
--i;
}
}
printf("the total solutions:%d\n",count);
deleteArray(chose_array);
}

Answer 2

程序我就不写了，麻烦，思路：所有数相加为n，所有数-1相加为n，知道a为 n，取值即可。

Answer 3

先排序，如果n比较小，暴力搜索。如果n比较大，用回溯法可以

Answer 4

1+1=几