fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. int **result;
  6. int *colSize;
  7. int resultSize;
  8. int maxResult;
  9.  
  10. int compare(const void *a, const void *b) {
  11.     return (*(int*)a - *(int*)b);
  12. }
  13.  
  14. void backtrack(int* nums, int numsSize, int target, int start, int* path, int pathSize, int sum) {
  15.     if (sum == target) {
  16.         // 保存当前路径到结果中
  17.         int *temp = (int*)malloc(pathSize * sizeof(int));
  18.         memcpy(temp, path, pathSize * sizeof(int));
  19.         if (resultSize >= maxResult) {
  20.             maxResult *= 2;
  21.             result = (int**)realloc(result, maxResult * sizeof(int*));
  22.             colSize = (int*)realloc(colSize, maxResult * sizeof(int));
  23.         }
  24.         result[resultSize] = temp;
  25.         colSize[resultSize] = pathSize;
  26.         resultSize++;
  27.         return;
  28.     }
  29.     if (sum > target) {
  30.         return;
  31.     }
  32.     for (int i = start; i < numsSize; i++) {
  33.         // 跳过重复元素
  34.         if (i > start && nums[i] == nums[i-1]) {
  35.             continue;
  36.         }
  37.         path[pathSize] = nums[i];
  38.         backtrack(nums, numsSize, target, i + 1, path, pathSize + 1, sum + nums[i]);
  39.     }
  40. }
  41.  
  42. int main() {
  43.     int numsSize;
  44.     scanf("%d", &numsSize);
  45.     int *nums = (int*)malloc(numsSize * sizeof(int));
  46.     for (int i = 0; i < numsSize; i++) {
  47.         scanf("%d", &nums[i]);
  48.     }
  49.     int target;
  50.     scanf("%d", &target);
  51.  
  52.     qsort(nums, numsSize, sizeof(int), compare);
  53.  
  54.     resultSize = 0;
  55.     maxResult = 16;
  56.     result = (int**)malloc(maxResult * sizeof(int*));
  57.     colSize = (int*)malloc(maxResult * sizeof(int));
  58.  
  59.     int *path = (int*)malloc(30 * sizeof(int)); // 假设组合长度不超过30
  60.  
  61.     backtrack(nums, numsSize, target, 0, path, 0, 0);
  62.  
  63.     // 输出结果
  64.     for (int i = 0; i < resultSize; i++) {
  65.         printf("[");
  66.         for (int j = 0; j < colSize[i]; j++) {
  67.             if (j > 0) {
  68.                 printf(",");
  69.             }
  70.             printf("%d", result[i][j]);
  71.         }
  72.         printf("]\n");
  73.     }
  74.  
  75.     // 释放内存
  76.     free(path);
  77.     for (int i = 0; i < resultSize; i++) {
  78.         free(result[i]);
  79.     }
  80.     free(result);
  81.     free(colSize);
  82.     free(nums);
  83.  
  84.     return 0;
  85. }
Success #stdin #stdout 0s 5292KB
comments (?)
stdin
copy 
[2,5,2,1,2]
stdout
copy 
[]
https://ideone.com/n52CFy
language:
C (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!