Generate All Combinations Sum K in DSA C - Time & Space Complexity

Time Complexity: Generate All Combinations Sum K

O(n choose k * k)

Understanding Time Complexity

We want to understand how the time needed to find all combinations that add up to a target grows as the input size changes.

Specifically, how does the number of operations increase when we try to generate all possible combinations?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void backtrack(int start, int k, int target, int* candidates, int candidatesSize, int* combination, int combSize) {
    if (target == 0 && combSize == k) {
        // store combination
        return;
    }
    if (target < 0 || combSize > k) return;
    for (int i = start; i < candidatesSize; i++) {
        combination[combSize] = candidates[i];
        backtrack(i + 1, k, target - candidates[i], candidates, candidatesSize, combination, combSize + 1);
    }
}

This code tries all combinations of numbers from candidates to find those with length k that sum to target.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls exploring combinations by looping through candidates starting from current index.
• How many times: Potentially explores all subsets of size k, which can be many depending on input size.

How Execution Grows With Input

As input size n grows, the number of combinations of size k grows quickly.

Input Size (n)	Approx. Operations
10	About 252 combinations (if k=5)
20	About 15,504 combinations (if k=5)
30	About 142,506 combinations (if k=5)

Pattern observation: The number of combinations grows very fast, roughly like n choose k, which increases sharply as n increases.

Final Time Complexity

Time Complexity: O(n choose k * k)

This means the time grows roughly with the number of k-sized combinations from n elements, and each combination takes up to k steps to build.

Common Mistake

[X] Wrong: "The time complexity is just O(n) because we loop through the array once."

[OK] Correct: The code uses recursion to explore many combinations, not just a single pass, so the time grows much faster than linear.

Interview Connect

Understanding how recursive combination generation scales helps you explain your approach clearly and shows you grasp the cost of exploring many possibilities.

Self-Check

"What if we allowed repeated elements in combinations? How would the time complexity change?"