Combination Sum III - Practice Coding Problems

Combination Sum III - Problem

Array Backtracking Medium

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

Only numbers 1 through 9 are used
Each number is used at most once

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Input & Output

Example 1 — Basic Case

$ Input: k = 3, n = 7

› Output: [[1,2,4]]

💡 Note: Only one valid combination: 1 + 2 + 4 = 7, uses exactly 3 numbers from 1-9

Example 2 — Multiple Solutions

$ Input: k = 3, n = 9

› Output: [[1,2,6],[1,3,5],[2,3,4]]

💡 Note: Three valid combinations: 1+2+6=9, 1+3+5=9, and 2+3+4=9

Example 3 — No Solution

$ Input: k = 4, n = 1

› Output: []

💡 Note: Impossible: need 4 numbers but minimum sum is 1+2+3+4=10, which exceeds target 1

Constraints

2 ≤ k ≤ 9
1 ≤ n ≤ 60

Visualization

Tap to expand

Understanding the Visualization

Input

k=3 numbers needed, target sum n=7

Process

Find 3-number combinations from digits 1-9

Output

Return combinations that sum to 7

Key Takeaway

🎯 Key Insight: Use backtracking to build combinations incrementally and prune impossible paths early

Asked in

a Amazon 45 f Facebook 38 M Microsoft 32 G Google 28

The key insight is to use backtracking with early pruning to avoid generating invalid combinations. The backtracking approach builds combinations incrementally and prunes branches when the current sum exceeds the target or when it's impossible to reach the target with remaining numbers. Time: O(2^9), Space: O(k)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Generate All Combinations	O(C(9,k))	O(k)	Generate all possible k-combinations of numbers 1-9 and filter by sum
Backtracking with Pruning	O(2^9)	O(k)	Build combinations incrementally, pruning impossible paths early

Brute Force - Generate All Combinations — Algorithm Steps

Generate all combinations of k digits from 1-9
For each combination, calculate the sum
Keep combinations where sum equals n

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Create all combinations of k=3 from digits 1-9

Filter

Check which combinations sum to n=7

Result

Return valid combinations

Code -

solution.c — C

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

int result[1000][9];
int resultSizes[1000];
int resultCount = 0;

void generateCombinations(int start, int* combo, int comboSize, int k, int n) {
    if (comboSize == k) {
        int sum = 0;
        for (int i = 0; i < comboSize; i++) {
            sum += combo[i];
        }
        if (sum == n) {
            for (int i = 0; i < k; i++) {
                result[resultCount][i] = combo[i];
            }
            resultSizes[resultCount] = k;
            resultCount++;
        }
        return;
    }
    
    for (int i = start; i <= 9; i++) {
        combo[comboSize] = i;
        generateCombinations(i + 1, combo, comboSize + 1, k, n);
    }
}

void solution(int k, int n) {
    resultCount = 0;
    int combo[9];
    generateCombinations(1, combo, 0, k, n);
}

int main() {
    int k, n;
    scanf("%d", &k);
    scanf("%d", &n);
    
    solution(k, n);
    
    printf("[");
    for (int i = 0; i < resultCount; i++) {
        printf("[");
        for (int j = 0; j < resultSizes[i]; j++) {
            printf("%d", result[i][j]);
            if (j < resultSizes[i] - 1) printf(",");
        }
        printf("]");
        if (i < resultCount - 1) printf(",");
    }
    printf("]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(C(9,k))

Must generate all combinations of k elements from 9 digits

✓ Linear Growth

Space Complexity

O(k)

Recursion depth and temporary combination storage

✓ Linear Space

89.5K Views

Medium Frequency

~15 min Avg. Time

3.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Generate All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler