Question

How to find all possible combinations of numbers in an array to reach a given sum with C

Answer 1

#include <stdio.h>

#define MAX_COMBINATIONS 128
#define MAX_SIZE 128

void findCombinations(int *arr, int arrSize, int target, int index, int *currentCombination, int currentSize, int results[MAX_COMBINATIONS][MAX_SIZE], int *resultCount) {
    if (target == 0) {
        for (int i = 0; i < currentSize; i++) {
            results[*resultCount][i] = currentCombination[i];
        }
        results[*resultCount][currentSize] = -1; // Mark end of valid combination
        (*resultCount)++;
        return;
    }
    if (target < 0 || index >= arrSize) {
        return;
    }

    // Include current element
    currentCombination[currentSize] = arr[index];
    findCombinations(arr, arrSize, target - arr[index], index, currentCombination, currentSize + 1, results, resultCount);

    // Exclude current element
    findCombinations(arr, arrSize, target, index + 1, currentCombination, currentSize, results, resultCount);
}

void combinationSum(int *arr, int arrSize, int target, int results[MAX_COMBINATIONS][MAX_SIZE], int *resultCount) {
    int currentCombination[MAX_SIZE];
    *resultCount = 0;
    findCombinations(arr, arrSize, target, 0, currentCombination, 0, results, resultCount);
}

void printCombinations(int results[MAX_COMBINATIONS][MAX_SIZE], int resultCount) {
    for (int i = 0; i < resultCount; i++) {
        for (int j = 0; results[i][j] != -1; j++) {
            printf("%d ", results[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int arr[] = {2, 3, 5, 6};
    int target = 8;
    int results[MAX_COMBINATIONS][MAX_SIZE];
    int resultCount;

    combinationSum(arr, sizeof(arr) / sizeof(arr[0]), target, results, &resultCount);

    printf("Combinations that sum to %d:\n", target);
    printCombinations(results, resultCount);

    return 0;
}




/*
run:

Combinations that sum to 8:
2 2 2 2 
2 3 3 
2 6 
3 5 


*/

 

70+ SQL courses for beginners and professionals