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.

Practice

1. What is the main goal of the Generate All Combinations Sum K problem?

easy

A. Count the total number of elements in an array

B. Sort an array of numbers in ascending order

C. Find the maximum number in an array

D. Find all unique combinations of numbers that add up to a target sum K

Solution

1. Step 1: Understand the problem statement

   The problem asks to find all unique sets of numbers that add up exactly to a given sum K.

2. Step 2: Identify the goal

   The goal is to generate all possible combinations, not just one or count elements.

3. Final Answer:

   Find all unique combinations of numbers that add up to a target sum K -> Option D

4. Quick Check:

   Combination sum = find all sets adding to K [OK]

Hint: Focus on combinations that sum exactly to K [OK]

Common Mistakes:

• Confusing combination sum with sorting
• Looking for maximum instead of combinations
• Counting elements instead of sums

2. Which of the following is the correct way to start a recursive function header in C for generating combinations that sum to K from an array arr of size n?

easy

A. void generate(int arr[], int n, int target, int start, int currentSum, int combination[], int combSize)

B. int generate(int arr, int n, int target, int start, int currentSum, int combination[], int combSize)

C. void generate(int arr, int n, int target, int start, int currentSum, int combination[], int combSize)

D. int generate(int arr[], int n, int target, int start, int currentSum, int combination[], int combSize)

Solution

1. Step 1: Check parameter types for array and function return

   In C, arrays are passed as int arr[] and recursive functions for generating combinations usually return void.

2. Step 2: Verify function signature correctness

   void generate(int arr[], int n, int target, int start, int currentSum, int combination[], int combSize) correctly uses void return type and int arr[] for the array parameter.

3. Final Answer:

   void generate(int arr[], int n, int target, int start, int currentSum, int combination[], int combSize) -> Option A

4. Quick Check:

   Correct C syntax for recursive combination function [OK]

Hint: Use void return and array as int arr[] in C [OK]

Common Mistakes:

• Using int instead of int[] for array parameter
• Returning int instead of void for recursive function
• Missing array brackets in parameter

3. What will be the output combinations for the array [2, 3, 6, 7] and target sum 7 using combination sum logic?

medium

A. [[7], [2, 2, 3]]

B. [[7], [3, 4]]

C. [[2, 3, 6], [7]]

D. [[2, 2, 3], [6, 1]]

Solution

1. Step 1: Identify valid combinations summing to 7

   From the array, 7 alone is valid. Also, 2+2+3 = 7 is valid. 3+4 is invalid as 4 is not in array. 6+1 invalid as 1 not in array.

2. Step 2: Confirm combinations

   Valid combinations are [7] and [2, 2, 3].

3. Final Answer:

   [[7], [2, 2, 3]] -> Option A

4. Quick Check:

   Sum 7 from array = [7], [2,2,3] [OK]

Hint: Check sums only from given array elements [OK]

Common Mistakes:

• Including numbers not in the array
• Ignoring repeated elements allowed
• Mixing invalid sums

4. Given the following snippet, what is the bug that prevents correct generation of combinations summing to K?

void generate(int arr[], int n, int target, int start, int currentSum, int combination[], int combSize) {
    if (currentSum == target) {
        // print combination
        return;
    }
    for (int i = start; i < n; i++) {
        if (currentSum + arr[i] <= target) {
            combination[combSize] = arr[i];
            generate(arr, n, target, i, currentSum + arr[i], combination, combSize + 1);
        }
    }
}

medium

A. Incorrect base case condition for currentSum == target

B. Loop should start from 0 instead of start

C. Missing backtracking step to remove last element after recursion

D. Function should return int instead of void

Solution

1. Step 1: Analyze recursion and combination building

   The function adds elements to combination but never removes them after recursion, causing incorrect combinations.

2. Step 2: Identify missing backtracking

   Backtracking requires removing last added element after recursive call to explore other paths.

3. Final Answer:

   Missing backtracking step to remove last element after recursion -> Option C

4. Quick Check:

   Backtracking needs element removal after recursion [OK]

Hint: Always remove last element after recursive call [OK]

Common Mistakes:

• Not removing last element after recursion
• Wrong base case check
• Loop starting index error

5. You want to generate all unique combinations from array [1, 2, 3] that sum to 4. Which of the following modifications ensures no duplicate combinations appear when numbers can be reused multiple times?

hard

A. Sort the array and skip duplicates by checking if current element equals previous

B. In recursive calls, pass i as start index to allow reuse and avoid duplicates

C. In recursive calls, always pass 0 as start index to restart from beginning

D. Use a global visited array to mark elements used

Solution

1. Step 1: Understand reuse and duplicates in combinations

   Allowing reuse means next recursion starts from current index i, not 0, to avoid duplicate sets in different orders.

2. Step 2: Identify correct start index usage

   Passing i as start index allows reuse and prevents duplicates by not revisiting earlier elements.

3. Final Answer:

   In recursive calls, pass i as start index to allow reuse and avoid duplicates -> Option B

4. Quick Check:

   Start index = i to reuse and avoid duplicates [OK]

Hint: Pass current index as start to reuse elements [OK]

Common Mistakes:

• Restarting from 0 causing duplicates
• Using visited array unnecessarily
• Not sorting or skipping duplicates properly