这个问题我目前只知道递归的解法，欢迎大家提出非递归的解法^_^
1 #include <stdlib.h> 2 3 // 求某数组所有元素做加法或减法结果为某个值的问题递归解法，目前我不知道其他解法 4 void func(int* arr, int len, int sum, int i, int num, int* aux) 5 { 6 if(i == len) 7 { 8 if(sum == num) 9 { 10 for(int j = 0; j < len; j++) 11 printf("%c %2d ", aux[j]?'+':'-', arr[j]); 12 printf("= %d ", num); 13 } 14 return; 15 } 16 aux[i] = 1; 17 func(arr, len, sum+arr[i], i+1, num, aux); 18 aux[i] = 0; 19 func(arr, len, sum-arr[i], i+1, num, aux); 20 } 21 22 // 求某数组的子集之和某个值的问题的递归解法 23 void func_subset(int* arr, int len, int sum, int i, int num, int* aux) 24 { 25 if(i == len) 26 { 27 if(sum == num) 28 { 29 for(int j = 0; j < len; j++) 30 aux[j]?printf("+ %2d ", arr[j]):printf(" ", arr[j]); 31 printf("= %d ", num); 32 } 33 return; 34 } 35 aux[i] = 1; 36 func_subset(arr, len, sum+arr[i], i+1, num, aux); 37 aux[i] = 0; 38 func_subset(arr, len, sum, i+1, num, aux); 39 } 40 41 int main() 42 { 43 int arr[] = {4, 8, 1, 1, 3, 3, 2, 2, 4}; 44 int* aux = new int[sizeof(arr)/4]; 45 printf(">> 求全部元素的加减运算结果为某个值的问题 "); 46 func(arr, sizeof(arr)/4, 0, 0, 24, aux); 47 printf(">> 求子集之和为某个值的问题 "); 48 func_subset(arr, sizeof(arr)/4, 0, 0, 24, aux); 49 delete[] aux; 50 51 getchar(); 52 return 0; 53 }
输出结果为：
>> 求全部元素的加减运算结果为某个值的问题 + 4 + 8 + 1 + 1 + 3 + 3 + 2 - 2 + 4 = 24 + 4 + 8 + 1 + 1 + 3 + 3 - 2 + 2 + 4 = 24 + 4 + 8 - 1 - 1 + 3 + 3 + 2 + 2 + 4 = 24 >> 求子集之和为某个值的问题 + 4 + 8 + 1 + 1 + 3 + 3 + 2 + 2 = 24 + 4 + 8 + 1 + 1 + 3 + 3 + 4 = 24 + 4 + 8 + 1 + 3 + 2 + 2 + 4 = 24 + 4 + 8 + 1 + 3 + 2 + 2 + 4 = 24 + 4 + 8 + 1 + 3 + 2 + 2 + 4 = 24 + 4 + 8 + 1 + 3 + 2 + 2 + 4 = 24 + 4 + 8 + 3 + 3 + 2 + 4 = 24 + 4 + 8 + 3 + 3 + 2 + 4 = 24 + 8 + 1 + 1 + 3 + 3 + 2 + 2 + 4 = 24