Generate All Combinations Sum K in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of combinations summing to K

What is the output of the following C code that generates all combinations of numbers from 1 to 4 that sum to 5?

DSA C

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

void backtrack(int start, int target, int *comb, int comb_len) {
    if (target == 0) {
        for (int i = 0; i < comb_len; i++) {
            printf("%d", comb[i]);
            if (i < comb_len - 1) printf(",");
        }
        printf("\n");
        return;
    }
    for (int i = start; i <= 4; i++) {
        if (i > target) break;
        comb[comb_len] = i;
        backtrack(i + 1, target - i, comb, comb_len + 1);
    }
}

int main() {
    int comb[10];
    backtrack(1, 5, comb, 0);
    return 0;
}

A

[1,4]
[2,3]

B

[1,4]
[2,3]
[5]

C

[1,4]
[2,3]
[1,2,2]

D

[1,4]
[2,3]
[3,2]

💡 Hint

Think about combinations of unique numbers from 1 to 4 that add up to 5.

The code generates combinations of unique numbers from 1 to 4 that sum to 5. The valid combinations are [1,4] and [2,3]. No single number 5 or repeated numbers like [1,2,2] are allowed.

🧠 Conceptual

intermediate

Understanding combination generation constraints

In generating all combinations of numbers from 1 to N that sum to K, which constraint ensures combinations do not repeat the same number multiple times?

A Allow numbers to be reused by resetting start index to 1 each time

B Use a global visited array to mark used numbers

C Sort the input array before generating combinations

D Increment the start index in recursive calls to avoid reusing numbers

💡 Hint

Think about how recursion controls which numbers can be chosen next.

Incrementing the start index in recursive calls ensures that each number is used at most once in a combination, preventing duplicates.

🔧 Debug

advanced

Identify the error in combination sum code

What error does the following C code produce when generating combinations summing to 7 from numbers 1 to 5? void backtrack(int start, int target, int *comb, int comb_len) { if (target == 0) { for (int i = 0; i < comb_len; i++) printf("%d ", comb[i]); printf("\n"); return; } for (int i = start; i <= 5; i++) { if (i >= target) break; comb[comb_len] = i; backtrack(i + 1, target - i, comb, comb_len + 1); } } int main() { int comb[10]; backtrack(1, 7, comb, 0); return 0; }

A Compilation error due to missing return type

B Infinite recursion causing stack overflow

C No output because the condition 'i >= target' skips valid combinations

D Outputs combinations including numbers greater than 7

💡 Hint

Check the condition that stops the loop inside backtrack.

The condition 'if (i >= target) break;' stops the loop even when i equals target, missing combinations where a single number equals the target.

🚀 Application

advanced

Number of combinations summing to K

How many unique combinations of numbers from 1 to 6 sum exactly to 6, assuming each number can be used only once?

A 5

B 6

C 4

D 7

💡 Hint

List all combinations carefully without repeating numbers.

The combinations are [6], [1,5], [2,4], [1,2,3], and [1,2,3] is unique. Total 5 unique combinations.

📝 Syntax

expert

Correct syntax for recursive combination function

Which option correctly declares a recursive function in C to generate all combinations summing to K?

A void backtrack(int start, int target, int *comb, int comb_len);

B void backtrack(int start, int target, int comb[], int comb_len) {}

C void backtrack(start int, target int, int *comb, int comb_len) {}

D int backtrack(int start, int target, int *comb, int comb_len) {}

💡 Hint

Check parameter types and syntax for array parameters in C.

Option B correctly declares the function with proper parameter types and array syntax. Option B is only a prototype, B has wrong return type usage, C has invalid parameter syntax.