fork download 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define ARRAYSIZE(a) (sizeof(a))/(sizeof(a[0]))
  5.  
  6. static int total_nodes;
  7.  
  8. // prints subset found
  9. void printSubset(int A[], int size)
  10. {
  11.     for(int i = 0; i < size; i++)
  12.     {
  13.         printf("%*d", 5, A[i]);
  14.     }
  15.  
  16.     printf("\n");
  17. }
  18.  
  19. // qsort compare function
  20. int comparator(const void *pLhs, const void *pRhs)
  21. {
  22.     int *lhs = (int *)pLhs;
  23.     int *rhs = (int *)pRhs;
  24.  
  25.     return *lhs > *rhs;
  26. }
  27.  
  28. // inputs
  29. // s            - set vector
  30. // t            - tuplet vector
  31. // s_size       - set size
  32. // t_size       - tuplet size so far
  33. // sum          - sum so far
  34. // ite          - nodes count
  35. // target_sum   - sum to be found
  36. void subset_sum(int s[], int t[],
  37.                 int s_size, int t_size,
  38.                 int sum, int ite,
  39.                 int const target_sum)
  40. {
  41.     total_nodes++;
  42.  
  43.     if( target_sum == sum )
  44.     {
  45.         // We found sum
  46.         printSubset(t, t_size);
  47.  
  48.         // constraint check
  49.         if( ite + 1 < s_size && sum - s[ite] + s[ite+1] <= target_sum )
  50.         {
  51.             // Exclude previous added item and consider next candidate
  52.             subset_sum(s, t, s_size, t_size-1, sum - s[ite], ite + 1, target_sum);
  53.         }
  54.         return;
  55.     }
  56.     else
  57.     {
  58.         // constraint check
  59.         if( ite < s_size && sum + s[ite] <= target_sum )
  60.         {
  61.             // generate nodes along the breadth
  62.             for( int i = ite; i < s_size; i++ )
  63.             {
  64.                 t[t_size] = s[i];
  65.  
  66.                 if( sum + s[i] <= target_sum )
  67.                 {
  68.                     // consider next level node (along depth)
  69.                     subset_sum(s, t, s_size, t_size + 1, sum + s[i], i + 1, target_sum);
  70.                 }
  71.             }
  72.         }
  73.     }
  74. }
  75.  
  76. // Wrapper that prints subsets that sum to target_sum
  77. void generateSubsets(int s[], int size, int target_sum)
  78. {
  79.     int *tuplet_vector = (int *)malloc(size * sizeof(int));
  80.  
  81.     int total = 0;
  82.  
  83.     // sort the set
  84.     qsort(s, size, sizeof(int), &comparator);
  85.  
  86.     for( int i = 0; i < size; i++ )
  87.     {
  88.         total += s[i];
  89.     }
  90.  
  91.     if( s[0] <= target_sum && total >= target_sum )
  92.     {
  93.  
  94.         subset_sum(s, tuplet_vector, size, 0, 0, 0, target_sum);
  95.  
  96.     }
  97.  
  98.     free(tuplet_vector);
  99. }
  100.  
  101. int main()
  102. {
  103.     int weights[] = {15, 22, 14, 26, 32, 9, 16, 8};
  104.     int target = 53;
  105.  
  106.     int size = ARRAYSIZE(weights);
  107.  
  108.     generateSubsets(weights, size, target);
  109.  
  110.     printf("Nodes generated %d\n", total_nodes);
  111.  
  112.     return 0;
  113. }
Success #stdin #stdout 0s 2424KB
comments (?)
stdin 
Standard input is empty
stdout 
    8    9   14   22
    8   14   15   16
   15   16   22
Nodes generated 68
https://ideone.com/g4BWni
language:
C99 (gcc 8.3)
created:
10 years 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!