Generate All Combinations Sum K in DSA C

Mental Model

Find all groups of numbers from a list that add up exactly to a target sum by trying each number and exploring further choices.

Analogy: Imagine you have a box of different colored beads and want to pick some beads so their total weight is exactly a certain number. You try picking one bead, then see if adding more beads can reach the target weight, or backtrack and try a different bead.

Candidates: [2, 3, 6, 7]
Target sum: 7
Start -> [] (empty combination)
Try 2 -> [2]
Try 2 again -> [2 -> 2]
Try 3 -> [3]
Try 7 -> [7]

Dry Run Walkthrough

Input: candidates: [2, 3, 6, 7], target sum: 7

Goal: Find all combinations of candidates that sum to 7

Step 1: Start with empty combination and target 7

[] (target=7)

Why: We begin with no numbers chosen and full target to reach

Step 2: Pick 2, reduce target to 5, explore further

[2] (target=5)

Why: Try including 2 and see if we can reach target by adding more

Step 3: Pick 2 again, reduce target to 3

[2 -> 2] (target=3)

Why: We can reuse numbers, so try 2 again

Step 4: Pick 3, reduce target to 0, found valid combination

[2 -> 2 -> 3] (target=0)

Why: Sum matches target, save this combination

Step 5: Backtrack to [2 -> 2], try next candidate 6 (too big), discard

[2 -> 2] (target=3)

Why: 6 is larger than remaining target, skip

Step 6: Backtrack to [2], try next candidate 3, reduce target to 2

[2 -> 3] (target=2)

Why: Try next candidate after 2

Step 7: Try 3 again (too big), discard

[2 -> 3] (target=2)

Why: 3 is larger than remaining target, skip

Step 8: Backtrack to [], try candidate 3, reduce target to 4

[3] (target=4)

Why: Try starting with 3

Step 9: Try 3 again, reduce target to 1

[3 -> 3] (target=1)

Why: Reuse 3

Step 10: Try 6 (too big), discard

[3 -> 3] (target=1)

Why: 6 is larger than remaining target, skip

Step 11: Try 7 (too big), discard

[3 -> 3] (target=1)

Why: 7 is larger than remaining target, skip

Step 12: Backtrack to [], try candidate 6, reduce target to 1

[6] (target=1)

Why: Try starting with 6

Step 13: Try 6 again (too big), discard

[6] (target=1)

Why: 6 is larger than remaining target, skip

Step 14: Try 7 (too big), discard

[6] (target=1)

Why: 7 is larger than remaining target, skip

Step 15: Backtrack to [], try candidate 7, reduce target to 0, found valid combination

[7] (target=0)

Why: Sum matches target, save this combination

Result:

[2 -> 2 -> 3] and [7]

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Node for storing one combination
typedef struct Node {
    int *combination;
    int size;
    struct Node *next;
} Node;

// Append new combination to result list
void append(Node **head, int *comb, int size) {
    Node *new_node = (Node*)malloc(sizeof(Node));
    new_node->combination = (int*)malloc(size * sizeof(int));
    for (int i = 0; i < size; i++) {
        new_node->combination[i] = comb[i];
    }
    new_node->size = size;
    new_node->next = NULL;
    if (*head == NULL) {
        *head = new_node;
    } else {
        Node *temp = *head;
        while (temp->next != NULL) temp = temp->next;
        temp->next = new_node;
    }
}

// Recursive helper to find combinations
void backtrack(int *candidates, int candidatesSize, int target, int start, int *comb, int combSize, Node **result) {
    if (target == 0) {
        append(result, comb, combSize); // save valid combination
        return;
    }
    for (int i = start; i < candidatesSize; i++) {
        if (candidates[i] > target) continue; // skip if candidate too big
        comb[combSize] = candidates[i];
        backtrack(candidates, candidatesSize, target - candidates[i], i, comb, combSize + 1, result); // reuse i
    }
}

// Print all combinations
void printResult(Node *head) {
    Node *curr = head;
    while (curr != NULL) {
        for (int i = 0; i < curr->size; i++) {
            printf("%d", curr->combination[i]);
            if (i < curr->size - 1) printf(" -> ");
        }
        printf(" -> null\n");
        curr = curr->next;
    }
}

int main() {
    int candidates[] = {2, 3, 6, 7};
    int target = 7;
    int candidatesSize = sizeof(candidates) / sizeof(candidates[0]);
    int *comb = (int*)malloc(target * sizeof(int));
    Node *result = NULL;

    backtrack(candidates, candidatesSize, target, 0, comb, 0, &result);
    printResult(result);

    free(comb);
    // Free result list omitted for brevity
    return 0;
}

if (target == 0) { append(result, comb, combSize); return; }

save combination when sum matches target

for (int i = start; i < candidatesSize; i++) { if (candidates[i] > target) continue;

skip candidates larger than remaining target

comb[combSize] = candidates[i]; backtrack(candidates, candidatesSize, target - candidates[i], i, comb, combSize + 1, result);

choose candidate and recurse with reduced target, allowing reuse

Output

2 -> 2 -> 3 -> null

7 -> null

Complexity Analysis

Time: O(2^n) because each candidate can be chosen or not, leading to exponential combinations

Space: O(k) for recursion stack and combination storage where k is max depth (target/min candidate)

vs Alternative: Compared to brute force checking all subsets, backtracking prunes paths early when sum exceeds target, saving time

Edge Cases

empty candidates array

no combinations found, result remains empty

DSA C

for (int i = start; i < candidatesSize; i++) { if (candidates[i] > target) continue;

target is zero

empty combination is valid and returned immediately

DSA C

if (target == 0) { append(result, comb, combSize); return; }

candidates contain duplicates

duplicates are allowed and can appear multiple times in combinations

DSA C

backtrack(candidates, candidatesSize, target - candidates[i], i, comb, combSize + 1, result);

When to Use This Pattern

When asked to find all groups of numbers that sum to a target, especially allowing reuse, use backtracking to explore choices and prune invalid paths.

Common Mistakes

Mistake: Not allowing reuse of the same candidate by incrementing start index incorrectly
Fix: Pass 'i' as start index in recursive call to allow reuse instead of 'i + 1'

Mistake: Not checking if candidate is greater than remaining target before recursion
Fix: Add condition to skip candidates larger than target to prune search early

Summary

Find all combinations of numbers that add up exactly to a target sum.

Use when you need every possible group of numbers summing to a value, allowing repeats.

Try each number, reduce target, and backtrack when sum is reached or exceeded.