Combinations - Practice Coding Problems

Combinations - Problem

Backtracking Medium

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].

You may return the answer in any order.

A combination is a selection of items without regard to the order of selection.

Input & Output

Example 1 — Basic Case

$ Input: n = 4, k = 2

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

💡 Note: All possible combinations of 2 numbers from range [1,4]: choose 2 from {1,2,3,4}

Example 2 — Single Element

$ Input: n = 1, k = 1

› Output: [[1]]

💡 Note: Only one way to choose 1 number from range [1,1]: just [1]

Example 3 — Choose All

$ Input: n = 3, k = 3

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

💡 Note: Only one way to choose all 3 numbers from range [1,3]: take everything

Constraints

1 ≤ n ≤ 20
1 ≤ k ≤ n

Visualization

Tap to expand

Understanding the Visualization

Input

n=4, k=2 means choose 2 numbers from {1,2,3,4}

Process

Generate all possible combinations systematically

Output

Return all valid k-sized combinations

Key Takeaway

🎯 Key Insight: Use backtracking to systematically build combinations one element at a time

Asked in

G Google 35 a Amazon 28 M Microsoft 22 f Facebook 18

The key insight is to use backtracking to generate combinations incrementally. Build each combination one number at a time, and when we reach the target size k, add it to the result. Best approach is backtracking with Time: O(C(n,k) × k), Space: O(k).

Common Approaches

Approach	Time	Space	Notes
✓ Backtracking	O(C(n,k) × k)	O(k)	Build combinations incrementally by making choices and backtracking
Brute Force - Generate All Subsets	O(2ⁿ × n)	O(2ⁿ × k)	Generate all possible subsets and filter those with exactly k elements

Backtracking — Algorithm Steps

Start with empty combination and current number 1
For each number, try including it in combination
When combination size equals k, add to result
Backtrack and try next possibilities

Visualization

Tap to expand

Step-by-Step Walkthrough

Choose

Add a number to current combination

Recurse

Continue building with remaining choices

Backtrack

Remove number and try next possibility

Code -

solution.c — C

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

int result[1000][20];
int resultSize = 0;
int temp[20];
int tempSize = 0;

void backtrack(int start, int n, int k) {
    // Base case: if we have k numbers, add to result
    if (tempSize == k) {
        for (int i = 0; i < k; i++) {
            result[resultSize][i] = temp[i];
        }
        resultSize++;
        return;
    }
    
    // Try each number from start to n
    for (int i = start; i <= n; i++) {
        // Choose: add current number
        temp[tempSize++] = i;
        // Recurse with next starting point
        backtrack(i + 1, n, k);
        // Backtrack: remove current number
        tempSize--;
    }
}

void solution(int n, int k) {
    resultSize = 0;
    tempSize = 0;
    backtrack(1, n, k);
    
    printf("[");
    for (int i = 0; i < resultSize; i++) {
        printf("[");
        for (int j = 0; j < k; j++) {
            printf("%d", result[i][j]);
            if (j < k - 1) printf(",");
        }
        printf("]");
        if (i < resultSize - 1) printf(",");
    }
    printf("]\n");
}

int main() {
    int n, k;
    scanf("%d", &n);
    scanf("%d", &k);
    solution(n, k);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(C(n,k) × k)

Generate C(n,k) combinations, each taking O(k) time to copy

✓ Linear Growth

Space Complexity

O(k)

Recursion depth is at most k levels, plus O(k) for current combination

✓ Linear Space

32.0K Views

Medium Frequency

~15 min Avg. Time

890 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

Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler