Combinations

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 combinations in any order.

What to notice first

• A combination is a selection where order does not matter: [1,2] and [2,1] are the same.
• The total number of combinations is C(n,k) = n! / (k!(n-k)!).
• You must generate all possible ways to choose exactly k items from n items without repetition.

Examples

Input	Output	Explanation
n=4, k=2	[[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]	6 unique combinations of 2 from 4
n=1, k=1	[[1]]	Only one way to choose 1 from 1
n=5, k=3	10 combinations	C(5,3) = 10 total combinations

Constraints

• 1 <= n <= 20
• 1 <= k <= n

Real-World Applications

Where this pattern appears

• Lottery number selection — finding all possible lottery ticket combinations from a pool of numbers.
• Course scheduling — selecting k electives from n available courses.
• Team formation — choosing k people from a group of n candidates where roles don’t matter.
• Testing combinations — generating all possible feature flag combinations for testing or A/B testing strategies.

Complexity Comparison

Approach	Time	Space	Implementation	Best When
Backtracking	O(C(n,k) * k)	O(C(n,k) * k)	Recursive, intuitive	Want clear, readable recursive solution
Iterative	O(C(n,k) * k)	O(C(n,k) * k)	Iterative, uses state machine	Prefer avoiding recursion overhead

Which approach should you learn first?

• Pick Backtracking if you are learning the decision tree pattern.
• Pick Iterative if you prefer avoiding recursion or want to understand the next-permutation technique.

Most Common

Backtracking

O(C(n,k) * k) time · O(C(n,k) * k) space

Iterative

Next Combination

O(C(n,k) * k) time · O(C(n,k) * k) space

Approach 1: Backtracking (Recommended)

★ Recommended

Use a decision tree where at each level we choose whether to include a number or not. Start from 1, and at each number decide whether to include it in the current combination. If we include it, recursively build combinations for the remaining k-1 slots from the remaining numbers.

The key insight is choose, explore, unchoose — this allows us to explore all possibilities without managing a separate “used” set.

⏱ Time O(C(n,k) * k) C(n,k) combos, k per combo 💾 Space O(C(n,k) * k) Result storage

Step-by-step Example

Input: n = 4, k = 2

Level	Current	Explore	Decision
0	[]	Start from 1	Choose 1?
1	[1]	Continue from 2	Choose from [2,3,4]?
2	[1,2]	k=2 reached	Save [1,2] ✓
2	[1,3]	k=2 reached	Save [1,3] ✓
2	[1,4]	k=2 reached	Save [1,4] ✓
1	[2]	Continue from 3	Choose from [3,4]?
2	[2,3]	k=2 reached	Save [2,3] ✓
2	[2,4]	k=2 reached	Save [2,4] ✓
1	[3]	Continue from 4	Choose 4?
2	[3,4]	k=2 reached	Save [3,4] ✓

Pseudocode

function combinationsBacktracking(n, k):
    result = []

    function backtrack(start, current):
        if len(current) == k:
            result.append(copy of current)
            return

        for i from start to n:
            current.append(i)
            backtrack(i + 1, current)
            current.pop()

    backtrack(1, [])
    return result

Solution Code

Python

combinations_backtracking.py

from typing import List


def combinations_backtracking(n: int, k: int) -> List[List[int]]:
    """
    Generate all combinations of k numbers from 1 to n using backtracking.
    Time: O(C(n,k) * k), Space: O(C(n,k) * k) for result
    """
    result = []

    def backtrack(start: int, current: List[int]) -> None:
        # Base case: we've selected k numbers
        if len(current) == k:
            result.append(current[:])  # Make a copy
            return

        # Explore: try each remaining number
        for i in range(start, n + 1):
            # Choose
            current.append(i)
            # Explore
            backtrack(i + 1, current)
            # Unchoose
            current.pop()

    backtrack(1, [])
    return result


print(combinations_backtracking(4, 2))  # [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]
print(combinations_backtracking(1, 1))  # [[1]]
print(combinations_backtracking(5, 3))  # 10 combinations

C++

combinations_backtracking.cpp

#include <vector>
using namespace std;

class Solution {
public:
    /**
     * Generate all combinations of k numbers from 1 to n using backtracking.
     * Time: O(C(n,k) * k), Space: O(C(n,k) * k) for result
     */
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> result;
        vector<int> current;
        backtrack(n, k, 1, current, result);
        return result;
    }

private:
    void backtrack(int n, int k, int start, vector<int>& current,
                   vector<vector<int>>& result) {
        // Base case: we've selected k numbers
        if (current.size() == k) {
            result.push_back(current);
            return;
        }

        // Explore: try each remaining number
        for (int i = start; i <= n; i++) {
            // Choose
            current.push_back(i);
            // Explore
            backtrack(n, k, i + 1, current, result);
            // Unchoose
            current.pop_back();
        }
    }
};

// Test
int main() {
    Solution sol;
    vector<vector<int>> result = sol.combine(4, 2);
    // Output: [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]
    return 0;
}

Java

CombinationsBacktracking.java

import java.util.*;

public class CombinationsBacktracking {
    /**
     * Generate all combinations of k numbers from 1 to n using backtracking.
     * Time: O(C(n,k) * k), Space: O(C(n,k) * k) for result
     */
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> current = new ArrayList<>();
        backtrack(n, k, 1, current, result);
        return result;
    }

    private void backtrack(int n, int k, int start, List<Integer> current,
                          List<List<Integer>> result) {
        // Base case: we've selected k numbers
        if (current.size() == k) {
            result.add(new ArrayList<>(current));
            return;
        }

        // Explore: try each remaining number
        for (int i = start; i <= n; i++) {
            // Choose
            current.add(i);
            // Explore
            backtrack(n, k, i + 1, current, result);
            // Unchoose
            current.remove(current.size() - 1);
        }
    }

    public static void main(String[] args) {
        CombinationsBacktracking sol = new CombinationsBacktracking();
        System.out.println(sol.combine(4, 2));
        // Output: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
    }
}

JavaScript

combinations_backtracking.js

/**
 * Generate all combinations of k numbers from 1 to n using backtracking.
 * Time: O(C(n,k) * k), Space: O(C(n,k) * k) for result
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
function combinationsBacktracking(n, k) {
    const result = [];

    function backtrack(start, current) {
        // Base case: we've selected k numbers
        if (current.length === k) {
            result.push([...current]);
            return;
        }

        // Explore: try each remaining number
        for (let i = start; i <= n; i++) {
            // Choose
            current.push(i);
            // Explore
            backtrack(i + 1, current);
            // Unchoose
            current.pop();
        }
    }

    backtrack(1, []);
    return result;
}

console.log(combinationsBacktracking(4, 2));
// Output: [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]

Rust

combinations_backtracking.rs

pub fn combinations_backtracking(n: i32, k: i32) -> Vec<Vec<i32>> {
    let mut result = vec![];
    let mut current = vec![];
    backtrack(n, k, 1, &mut current, &mut result);
    result
}

fn backtrack(n: i32, k: i32, start: i32, current: &mut Vec<i32>, result: &mut Vec<Vec<i32>>) {
    // Base case: we've selected k numbers
    if current.len() == k as usize {
        result.push(current.clone());
        return;
    }

    // Explore: try each remaining number
    for i in start..=n {
        // Choose
        current.push(i);
        // Explore
        backtrack(n, k, i + 1, current, result);
        // Unchoose
        current.pop();
    }
}

fn main() {
    let result = combinations_backtracking(4, 2);
    println!("{:?}", result);
    // Output: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
}

Go

combinations_backtracking.go

package main

import "fmt"

func combinationsBacktracking(n int, k int) [][]int {
  var result [][]int
  var current []int

  var backtrack func(int)
  backtrack = func(start int) {
    // Base case: we've selected k numbers
    if len(current) == k {
      combo := make([]int, k)
      copy(combo, current)
      result = append(result, combo)
      return
    }

    // Explore: try each remaining number
    for i := start; i <= n; i++ {
      // Choose
      current = append(current, i)
      // Explore
      backtrack(i + 1)
      // Unchoose
      current = current[:len(current)-1]
    }
  }

  backtrack(1)
  return result
}

func main() {
  fmt.Println(combinationsBacktracking(4, 2))
  // Output: [[1 2] [1 3] [1 4] [2 3] [2 4] [3 4]]
}

Approach 2: Iterative (Next Combination)

🎯 Interview Favourite

Generate combinations iteratively using a state machine approach. Start with the first k numbers [1, 2, ..., k]. At each step, find the rightmost number that can be incremented (one that is not yet at its maximum value), increment it, and reset all numbers to its right.

This approach mimics the “next combination” concept, similar to how you would manually enumerate combinations on paper.

⏱ Time O(C(n,k) * k) C(n,k) combos, k per combo 💾 Space O(C(n,k) * k) Result storage

Step-by-step Example

Input: n = 4, k = 2

Combo	Action	Next
[1,2]	Save, then find rightmost incrementable: index 1	Increment combo[1] from 2 to 3
[1,3]	Save, then find rightmost incrementable: index 1	Increment combo[1] from 3 to 4
[1,4]	Save, then find rightmost incrementable: index 1, but 4 is max	Backtrack to index 0
[2,3]	Increment combo[0] from 1 to 2, reset combo[1] to 3	Save, find rightmost
[2,4]	Save, then find rightmost incrementable: index 1	Done after processing all
[3,4]	Continue until rightmost element reaches n

Pseudocode

function combinationsIterative(n, k):
    result = []
    combo = [1, 2, ..., k]

    while true:
        result.append(copy of combo)

        # Find the rightmost number that can be incremented
        i = k - 1
        while i >= 0 and combo[i] == n - k + i + 1:
            i--

        if i < 0:
            break

        # Increment and reset
        combo[i]++
        for j from i+1 to k:
            combo[j] = combo[j-1] + 1

    return result

Solution Code

Python

combinations_iterative.py

from typing import List


def combinations_iterative(n: int, k: int) -> List[List[int]]:
    """
    Generate all combinations of k numbers from 1 to n using iterative approach.
    Time: O(C(n,k) * k), Space: O(C(n,k) * k) for result
    """
    result = []
    combo = list(range(1, k + 1))

    while True:
        result.append(combo[:])

        # Find the rightmost number that can be incremented
        i = k - 1
        while i >= 0 and combo[i] == n - k + i + 1:
            i -= 1

        if i < 0:
            break

        # Increment and reset
        combo[i] += 1
        for j in range(i + 1, k):
            combo[j] = combo[j - 1] + 1

    return result


print(combinations_iterative(4, 2))  # [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]
print(combinations_iterative(1, 1))  # [[1]]
print(combinations_iterative(5, 3))  # 10 combinations

C++

combinations_iterative.cpp

#include <vector>
using namespace std;

class Solution {
public:
    /**
     * Generate all combinations of k numbers from 1 to n using iterative approach.
     * Time: O(C(n,k) * k), Space: O(C(n,k) * k) for result
     */
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> result;
        vector<int> combo(k);

        // Initialize with [1, 2, ..., k]
        for (int i = 0; i < k; i++) {
            combo[i] = i + 1;
        }

        while (true) {
            result.push_back(combo);

            // Find the rightmost number that can be incremented
            int i = k - 1;
            while (i >= 0 && combo[i] == n - k + i + 1) {
                i--;
            }

            if (i < 0) break;

            // Increment and reset
            combo[i]++;
            for (int j = i + 1; j < k; j++) {
                combo[j] = combo[j - 1] + 1;
            }
        }

        return result;
    }
};

// Test
int main() {
    Solution sol;
    vector<vector<int>> result = sol.combine(4, 2);
    // Output: [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]
    return 0;
}

Java

CombinationsIterative.java

import java.util.*;

public class CombinationsIterative {
    /**
     * Generate all combinations of k numbers from 1 to n using iterative approach.
     * Time: O(C(n,k) * k), Space: O(C(n,k) * k) for result
     */
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        int[] combo = new int[k];

        // Initialize with [1, 2, ..., k]
        for (int i = 0; i < k; i++) {
            combo[i] = i + 1;
        }

        while (true) {
            List<Integer> current = new ArrayList<>();
            for (int num : combo) {
                current.add(num);
            }
            result.add(current);

            // Find the rightmost number that can be incremented
            int i = k - 1;
            while (i >= 0 && combo[i] == n - k + i + 1) {
                i--;
            }

            if (i < 0) break;

            // Increment and reset
            combo[i]++;
            for (int j = i + 1; j < k; j++) {
                combo[j] = combo[j - 1] + 1;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        CombinationsIterative sol = new CombinationsIterative();
        System.out.println(sol.combine(4, 2));
        // Output: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
    }
}

JavaScript

combinations_iterative.js

/**
 * Generate all combinations of k numbers from 1 to n using iterative approach.
 * Time: O(C(n,k) * k), Space: O(C(n,k) * k) for result
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
function combinationsIterative(n, k) {
    const result = [];
    const combo = Array.from({ length: k }, (_, i) => i + 1);

    while (true) {
        result.push([...combo]);

        // Find the rightmost number that can be incremented
        let i = k - 1;
        while (i >= 0 && combo[i] === n - k + i + 1) {
            i--;
        }

        if (i < 0) break;

        // Increment and reset
        combo[i]++;
        for (let j = i + 1; j < k; j++) {
            combo[j] = combo[j - 1] + 1;
        }
    }

    return result;
}

console.log(combinationsIterative(4, 2));
// Output: [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]

Rust

combinations_iterative.rs

pub fn combinations_iterative(n: i32, k: i32) -> Vec<Vec<i32>> {
    let mut result = vec![];
    let mut combo: Vec<i32> = (1..=k).collect();

    loop {
        result.push(combo.clone());

        // Find the rightmost number that can be incremented
        let mut i = (k - 1) as usize;
        loop {
            if combo[i] == n - k + (i as i32) + 1 {
                if i == 0 {
                    return result;
                }
                i -= 1;
            } else {
                break;
            }
        }

        // Increment and reset
        combo[i] += 1;
        for j in (i + 1)..(k as usize) {
            combo[j] = combo[j - 1] + 1;
        }
    }
}

fn main() {
    let result = combinations_iterative(4, 2);
    println!("{:?}", result);
    // Output: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
}

Go

combinations_iterative.go

package main

import "fmt"

func combinationsIterative(n int, k int) [][]int {
  var result [][]int
  combo := make([]int, k)

  // Initialize with [1, 2, ..., k]
  for i := 0; i < k; i++ {
    combo[i] = i + 1
  }

  for {
    // Save current combination
    current := make([]int, k)
    copy(current, combo)
    result = append(result, current)

    // Find the rightmost number that can be incremented
    i := k - 1
    for i >= 0 && combo[i] == n-k+i+1 {
      i--
    }

    if i < 0 {
      break
    }

    // Increment and reset
    combo[i]++
    for j := i + 1; j < k; j++ {
      combo[j] = combo[j-1] + 1
    }
  }

  return result
}

func main() {
  fmt.Println(combinationsIterative(4, 2))
  // Output: [[1 2] [1 3] [1 4] [2 3] [2 4] [3 4]]
}

Common mistakes

Watch for these pitfalls

• Forgetting to save a copy in backtracking; pushing a reference instead of a copy will result in all results pointing to the same list.
• Off-by-one errors in the iterative approach; the condition combo[i] == n - k + i + 1 checks whether combo[i] is at its maximum valid value.
• Failing to increment i correctly when finding the next incrementable position; it should be i + 1, not i.
• Not resetting the rest of the combination after incrementing; the combo[j] = combo[j-1] + 1 step is essential.

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

combinations_space_optimized.py

"""
Solution for Combinations
"""

def solve():
    """Implementation for approach 3 of Combinations"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

combinations_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Combinations
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

CombinationsSpaceOptimized.java

/**
 * Solution for Combinations
 * Approach 3
 */
public class CombinationsSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

combinations_space_optimized.js

/**
 * Solution for Combinations
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

combinations_space_optimized.rs

/// Solution for Combinations
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

combinations_space_optimized.go

package main

import "fmt"

// Solution for Combinations
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Permutations ↗ Medium #46
• Subsets ↗ Medium #78
• Combination Sum ↗ Medium #39
• Letter Combinations of a Phone Number ↗ Medium #17

Interview Tips

Key trade-offs to discuss

• Backtracking vs Iterative: Backtracking is easier to understand and code correctly; iterative is good if you want to show mastery of state machines.
• Time complexity awareness: C(n,k) grows very large; for n=20 and k=10, it’s about 184,756 combinations, so mentioning this in an interview shows awareness.
• Space optimization: The result list itself uses O(C(n,k) * k) space, which is unavoidable since we need to return all results.
• Follow-up — Combinations with Replacement: If asked to allow repeated elements, the approach is similar but the loop should start from i instead of i+1.

← Previous
#76 Minimum Window Substring Next
#78 Subsets →