Crack the Backend

Problem Statement

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 k distinct numbers; order does not matter (so [1,2] and [2,1] are the same combination).

We generate combinations without repetition: each number is used at most once, and we avoid duplicate sets by only choosing "next" numbers after the last chosen one (so we iterate from start to n and recurse with start = i + 1).

Key Observations

Backtracking: Maintain a path (current combination). When path.size() == k, add a copy to the result. Otherwise, for each i from start to n, add i to the path, recurse with start = i + 1 (so we only pick larger numbers and avoid duplicates), then remove i (backtrack).
By always advancing start, we never pick the same set in a different order. The number of combinations is C(n,k).

Approach

High-level: DFS with (start, path). If path.size() == k, add path to result. Else for i = start..n: path.add(i), dfs(i+1, path), path.remove.

Steps: dfs(start): if path.size() == k add copy and return. For i = start..n: path.add(i), dfs(i+1), path.remove(path.size()-1).

Implementation

Java

public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> result = new ArrayList<>();
    dfs(n, k, 1, new ArrayList<>(), result);
    return result;
}

void dfs(int n, int k, int start, List<Integer> path, List<List<Integer>> result) {

    if (path.size() == k) { result.add(new ArrayList<>(path)); return; }
    for (int i = start; i <= n; i++) {
        path.add(i);
        dfs(n, k, i + 1, path, result);
        path.remove(path.size() - 1);
    }
}

Test Cases

Example 1

Input

n = 4, k = 2

Expected

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

Explanation

All C(4,2) combinations.

Complexity Analysis

Time: O(C(n,k)).
Space: O(k).

Follow-ups

Combination Sum: reuse same number; sum to target.