Skip to main content
Talentd

Combinations - Solution & Explanation

MediumBacktracking25 min readAsked at: Amazon, Microsoft, Meta +5
Practice this problem

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.

 

Example 1:

Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.

Example 2:

Input: n = 1, k = 1
Output: [[1]]
Explanation: There is 1 choose 1 = 1 total combination.

 

Constraints:

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

Approach Overview

Problem Overview: Given two integers n and k, generate every possible combination of k numbers chosen from the range 1..n. Order inside a combination does not matter, so [1,2] and [2,1] represent the same result and only one should appear.

Approach 1: Backtracking (Time: O(C(n,k) * k), Space: O(k))

This is the standard solution and the one most interviewers expect. Use backtracking to build combinations incrementally. Start from a number, add it to a temporary list, and recursively choose the next numbers from the remaining range. When the current list size reaches k, record the combination. The key insight is that each recursive call restricts the next candidate range, preventing duplicates and preserving ascending order. The recursion depth never exceeds k, and the algorithm generates exactly C(n,k) valid combinations.

Pruning improves efficiency: if you already selected m numbers and there are fewer than k - m numbers left, you can stop exploring that branch. This avoids unnecessary recursive calls when the remaining elements cannot complete a valid combination.

Approach 2: Iterative Approach Using Bit Masking (Time: O(2^n * n), Space: O(k))

This method treats each subset of numbers as a binary mask. For every integer from 0 to (1 << n) - 1, the binary representation indicates which numbers are included. Count the set bits in the mask; if exactly k bits are set, build the corresponding combination by checking each bit position. This relies on bit manipulation and is conceptually simple because it enumerates all subsets.

The downside is that it explores the full subset space of size 2^n, even though only C(n,k) results are needed. For large n, this becomes inefficient compared to targeted generation. Still, it is useful when practicing subset enumeration or when bit operations simplify implementation.

Recommended for interviews: The backtracking approach is the expected solution. It directly models the combinatorial search and generates only valid results, giving optimal output-sensitive complexity of O(C(n,k) * k). Bit masking demonstrates knowledge of recursion alternatives and subset enumeration, but it is rarely the preferred production or interview solution.

Approach 1: Backtracking Approach

This method uses a backtracking technique, where we recursively build each combination by adding numbers incrementally and backtrack whenever we've constructed combinations of size k or cannot extend further.

This solution involves a recursive function backtrack that constructs combinations by adding candidates one by one and proceeds only if the current set can lead to a combination, which ensures our search tree doesn't explore invalid paths. Once a combination of size k is completed, it's stored in the result set.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(C(n, k) * k), where C(n, k) is the binomial coefficient. Each combination is built in O(k) time.
Space Complexity: O(k) due to the recursion stack storing the current combination.

Try this approach in the editor →

Approach 2: Iterative Approach Using Bit Masking

Bit masking provides a novel way to generate combinations by representing choice decisions (e.g., pick or skip) in binary. A bit mask is applied to the set of numbers [1...n], and for each bit position, if the bit is set, that number is included in the combination.

This code generates all possible bit masks for integers from 0 to 2n-1, checking for those that have exactly k bits set. The function __builtin_popcount is used to count the number of set bits in the mask, indicating how many items in the set are chosen for a combination.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(2n * n), as we iterate over all possible subsets of [1...n] and check the bit count.
Space Complexity: O(C(n, k) * k) for storing all combinations.

Try this approach in the editor →

Approach 3: Backtracking (Two Ways)

We design a function dfs(i), which represents starting the search from number i, with the current search path as t, and the answer as ans.

The execution logic of the function dfs(i) is as follows:

  • If the length of the current search path t equals k, then add the current search path to the answer and return.
  • If i \gt n, it means the search has ended, return.
  • Otherwise, we can choose to add the number i to the search path t, and then continue the search, i.e., execute dfs(i + 1), and then remove the number i from the search path t; or we do not add the number i to the search path t, and directly execute dfs(i + 1).

The above method is actually enumerating whether to select the current number or not, and then recursively searching the next number. We can also enumerate the next number j to be selected, where i leq j leq n. If the next number to be selected is j, then we add the number j to the search path t, and then continue the search, i.e., execute dfs(j + 1), and then remove the number j from the search path t.

In the main function, we start the search from number 1, i.e., execute dfs(1).

The time complexity is (C_n^k times k), and the space complexity is O(k). Here, C_n^k represents the combination number.

Similar problems:

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Approach 4: Default Approach

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Backtracking Approach

Time Complexity: O(C(n, k) * k), where C(n, k) is the binomial coefficient. Each combination is built in O(k) time.
Space Complexity: O(k) due to the recursion stack storing the current combination.

Iterative Approach Using Bit Masking

Time Complexity: O(2n * n), as we iterate over all possible subsets of [1...n] and check the bit count.
Space Complexity: O(C(n, k) * k) for storing all combinations.

Backtracking (Two Ways)—
Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
BacktrackingO(C(n,k) * k)O(k)Best general solution. Generates only valid combinations and scales well for typical constraints.
Iterative Bit MaskingO(2^n * n)O(k)Useful when practicing subset enumeration or when n is small.

Video Solution

Combinations - Leetcode 77 - Python • NeetCode • 95,115 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Combinations easy or hard?
Combinations is considered a medium-level problem because it requires understanding recursive backtracking and controlling the search space. The implementation is short, but recognizing the pattern and avoiding duplicate exploration requires practice.
Combinations Python/Java solution
Python and Java implementations typically use recursive backtracking. A helper function adds numbers from the current start index, pushes them into a list, and backtracks after exploring deeper states. The same logic translates easily across C++, Java, and JavaScript.
How to solve Combinations in O(n)?
Generating all combinations cannot be done in O(n) time because the output itself contains C(n,k) results. The optimal strategy is output-sensitive backtracking with complexity O(C(n,k) * k), which scales with the number of combinations produced.
What is the best approach for Combinations?
Backtracking is the most efficient and commonly expected approach. It builds combinations incrementally and stops exploring a branch once k elements are chosen. The algorithm generates exactly C(n,k) results with time complexity O(C(n,k) * k) and recursion depth O(k).
Is Combinations asked at Google/Amazon/Meta?
Combination generation problems appear frequently in interviews at companies like Amazon, Google, and Meta. They test understanding of backtracking, recursion trees, and pruning techniques used in combinatorial search problems.
What data structure is used in Combinations?
The typical solution uses recursion with a dynamic list or array to store the current combination. The algorithm also relies on the call stack for backtracking and sometimes bit masks when exploring subset-based approaches.
What is the time complexity of Combinations?
The optimal backtracking solution runs in O(C(n,k) * k) time because it generates every valid combination and copying each combination costs O(k). Space complexity is O(k) for the recursion stack excluding the output list.

Ready to solve this problem?

Practice Combinations with our built-in code editor and test cases.

Practice on FleetCode
Previous

Combination Sum

Next

Permutations