fork download
copy 
  1. #include <stdio.h>
  2.  
  3. #define MAX_X 100
  4.  
  5. // Function to count combinations using backtracking
  6. int countCombinations(int weights[], int start, int num_bags, int target_weight, int current_weight, int count) {
  7.     if (num_bags == 0) {
  8.         if (current_weight == target_weight) {
  9.             return 1;
  10.         }
  11.         return 0;
  12.     }
  13.  
  14.     if (start >= MAX_X) {
  15.         return 0;
  16.     }
  17.  
  18.     int ways = 0;
  19.  
  20.     // Include the current sack in the combination
  21.     ways += countCombinations(weights, start + 1, num_bags - 1, target_weight, current_weight + weights[start], count);
  22.  
  23.     // Exclude the current sack and move to the next
  24.     ways += countCombinations(weights, start + 1, num_bags, target_weight, current_weight, count);
  25.  
  26.     return ways;
  27. }
  28.  
  29. int main() {
  30.     int W, N, X;
  31.     int weights[MAX_X];
  32.  
  33.     // Read inputs
  34.     scanf("%d", &W);
  35.     scanf("%d %d", &N, &X);
  36.  
  37.     for (int i = 0; i < X; i++) {
  38.         scanf("%d", &weights[i]);
  39.     }
  40.  
  41.     // Compute the number of valid combinations
  42.     int result = countCombinations(weights, 0, N, W, 0, 0);
  43.  
  44.     // Print the result
  45.     printf("%d\n", result);
  46.  
  47.     return 0;
  48. }
Success #stdin #stdout 0s 5280KB
comments (?)
stdin
copy 
20
3 10
1 2 4 5 10 11 13 15 17 19
stdout
copy 
240
https://ideone.com/sYsdtd
language:
C (gcc 8.3)
created:
3 days 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!