Combinations solution and explanation
Google
Infosys
IBM
9 more videos on this problem
Combinations - Leetcode 77 - PythonNeetCode · 10:38 · 95K views
Combinations | INTUITIVE | Backtracking Template | Two Ways | Similar Problems | Leetcode-77codestorywithMIK · 18:37 · 32K views
Combinations - Leetcode 77 - Recursive Backtracking (Python)Greg Hogg · 7:56 · 15K views
LeetCode 77 | Combinations | Backtracking Algorithm Explained (Java + Debugging)Xavier Elon · 10:14 · 15K views
Leetcode 77 CombinationsJeevan Kumar - Cracckify · 9:57 · 2K views
Combinations - Leetcode 77 - JavaMastering Programming · 6:26 · 2K views
Combinations - LeetCode 77 - Python #backtracking #leetcode #combinationsDeepti Talesra · 11:18 · 1K views
Combinations (Leetcode Problem 77) Solution Explained - JavaHarVi · 4:44 · 1K views
COMBINATIONS | LEETCODE 77 | PYTHON BACKTRACKING SOLUTIONCracking FAANG · 14:24 · 1K views
Combination (LeetCode 77) || Full explanation in English || JAVA || Easy solution with BacktrackingHustle with a Mediocre · 17:51 · 821 views
The problem
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 <= 201 <= 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.
def combine(n, k):
def backtrack(start, curr):
if len(curr) == k:
result.append(curr[:])
return
for i in range(start, n+1):
curr.append(i)
backtrack(i+1, curr)
curr.pop()
result = []
backtrack(1, [])
return result
print(combine(4, 2))import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> result = new ArrayList<>();
backtrack(n, k, 1, new ArrayList<>(), result);
return result;
}
private void backtrack(int n, int k, int start, List<Integer> current, List<List<Integer>> result) {
if (current.size() == k) {
result.add(new ArrayList<>(current));
return;
}
for (int i = start; i <= n; ++i) {
current.add(i);
backtrack(n, k, i + 1, current, result);
current.remove(current.size() - 1);
}
}
public static void main(String[] args) {
Solution solution = new Solution();
List<List<Integer>> combinations = solution.combine(4, 2);
for (List<Integer> combo : combinations) {
System.out.println(combo);
}
}
}#include <iostream>
#include <vector>
void backtrack(int n, int k, int start, std::vector<int>& current, std::vector<std::vector<int>>& result) {
if (current.size() == k) {
result.push_back(current);
return;
}
for (int i = start; i <= n; ++i) {
current.push_back(i);
backtrack(n, k, i + 1, current, result);
current.pop_back();
}
}
std::vector<std::vector<int>> combine(int n, int k) {
std::vector<std::vector<int>> result;
std::vector<int> current;
backtrack(n, k, 1, current, result);
return result;
}
int main() {
int n = 4, k = 2;
std::vector<std::vector<int>> combinations = combine(n, k);
for (const auto& combo : combinations) {
std::cout << "[";
for (size_t i = 0; i < combo.size(); ++i) {
std::cout << combo[i];
if (i < combo.size() - 1) std::cout << ", ";
}
std::cout << "]\n";
}
return 0;
}function combine(n, k) {
const result = [];
const backtrack = (start, current) => {
if (current.length === k) {
result.push([...current]);
return;
}
for (let i = start; i <= n; i++) {
current.push(i);
backtrack(i + 1, current);
current.pop();
}
};
backtrack(1, []);
return result;
}
console.log(combine(4, 2));#include <stdio.h>
#include <stdlib.h>
void backtrack(int n, int k, int start, int* current, int curr_size, int** result, int* returnSize, int* returnColumnSizes) {
if (curr_size == k) {
result[*returnSize] = (int*) malloc(k * sizeof(int));
for (int i = 0; i < k; ++i) {
result[*returnSize][i] = current[i];
}
returnColumnSizes[*returnSize] = k;
(*returnSize)++;
return;
}
for (int i = start; i <= n; ++i) {
current[curr_size] = i;
backtrack(n, k, i + 1, current, curr_size + 1, result, returnSize, returnColumnSizes);
}
}
int** combine(int n, int k, int* returnSize, int** returnColumnSizes) {
int max_combinations = 1;
for (int i = 0; i < k; i++) {
max_combinations *= (n - i) / (i + 1);
}
int** result = (int**) malloc(max_combinations * sizeof(int*));
int* current = (int*) malloc(k * sizeof(int));
*returnSize = 0;
*returnColumnSizes = (int*) malloc(max_combinations * sizeof(int));
backtrack(n, k, 1, current, 0, result, returnSize, *returnColumnSizes);
free(current);
return result;
}
int main() {
int returnSize;
int* returnColumnSizes;
int n = 4, k = 2;
int** combinations = combine(n, k, &returnSize, &returnColumnSizes);
for (int i = 0; i < returnSize; i++) {
printf("[");
for (int j = 0; j < returnColumnSizes[i]; j++) {
printf("%d", combinations[i][j]);
if (j < returnColumnSizes[i] - 1) printf(", ");
}
printf("]\n");
free(combinations[i]);
}
free(combinations);
free(returnColumnSizes);
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<IList<int>> Combine(int n, int k) {
var result = new List<IList<int>>();
Backtrack(n, k, 1, new List<int>(), result);
return result;
}
private void Backtrack(int n, int k, int start, List<int> current, IList<IList<int>> result) {
if (current.Count == k) {
result.Add(new List<int>(current));
return;
}
for (int i = start; i <= n; ++i) {
current.Add(i);
Backtrack(n, k, i + 1, current, result);
current.RemoveAt(current.Count - 1);
}
}
public static void Main(string[] args) {
var solution = new Solution();
var combinations = solution.Combine(4, 2);
foreach (var combo in combinations) {
Console.WriteLine("[{0}]", string.Join(", ", combo));
}
}
}The Python implementation uses a local helper function backtrack to recursively explore possible combinations, leveraging Python's list's natural dynamic size for convenient management of the current list of numbers being explored.
Time Complexity: O(C(n, k) * k) since each combination is of size k.
Space Complexity: O(k) due to the recursion stack depth and space required to store k numbers for each combination.
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.
def combine(n, k):
result = []
for mask in range(1 << n):
if bin(mask).count('1') == k:
combo = [i + 1 for i in range(n) if mask & (1 << i)]
result.append(combo)
return result
print(combine(4, 2))import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> result = new ArrayList<>();
int total = 1 << n;
for (int mask = 0; mask < total; ++mask) {
if (Integer.bitCount(mask) == k) {
List<Integer> current = new ArrayList<>();
for (int i = 0; i < n; ++i) {
if ((mask & (1 << i)) != 0) {
current.add(i + 1);
}
}
result.add(current);
}
}
return result;
}
public static void main(String[] args) {
Solution solution = new Solution();
List<List<Integer>> combinations = solution.combine(4, 2);
for (List<Integer> combo : combinations) {
System.out.println(combo);
}
}
}#include <iostream>
#include <vector>
std::vector<std::vector<int>> combine(int n, int k) {
std::vector<std::vector<int>> result;
int total = 1 << n;
for (int mask = 0; mask < total; ++mask) {
if (__builtin_popcount(mask) == k) {
std::vector<int> current;
for (int i = 0; i < n; ++i) {
if (mask & (1 << i)) {
current.push_back(i + 1);
}
}
result.push_back(current);
}
}
return result;
}
int main() {
int n = 4, k = 2;
std::vector<std::vector<int>> combinations = combine(n, k);
for (const auto& combo : combinations) {
std::cout << "[";
for (size_t i = 0; i < combo.size(); ++i) {
std::cout << combo[i];
if (i < combo.size() - 1) std::cout << ", ";
}
std::cout << "]\n";
}
return 0;
}function combine(n, k) {
const result = [];
for (let mask = 0; mask < (1 << n); ++mask) {
if (mask.toString(2).split('0').join('').length === k) {
const current = [];
for (let i = 0; i < n; ++i) {
if (mask & (1 << i)) {
current.push(i + 1);
}
}
result.push(current);
}
}
return result;
}
console.log(combine(4, 2));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int** combine(int n, int k, int* returnSize, int** returnColumnSizes) {
int total = 1 << n;
*returnSize = 0;
int** result = (int**)malloc(1000 * sizeof(int*));
*returnColumnSizes = (int*)malloc(1000 * sizeof(int));
for (int mask = 0; mask < total; ++mask) {
if (__builtin_popcount(mask) == k) {
result[*returnSize] = (int*)malloc(k * sizeof(int));
int idx = 0;
for (int i = 0; i < n; ++i) {
if (mask & (1 << i)) {
result[*returnSize][idx++] = i + 1;
}
}
(*returnColumnSizes)[*returnSize] = k;
(*returnSize)++;
}
}
return result;
}
int main() {
int returnSize;
int* returnColumnSizes;
int n = 4, k = 2;
int** combinations = combine(n, k, &returnSize, &returnColumnSizes);
for (int i = 0; i < returnSize; i++) {
printf("[");
for (int j = 0; j < returnColumnSizes[i]; j++) {
printf("%d", combinations[i][j]);
if (j < returnColumnSizes[i] - 1) {
printf(", ");
}
}
printf("]\n");
free(combinations[i]);
}
free(combinations);
free(returnColumnSizes);
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<IList<int>> Combine(int n, int k) {
var result = new List<IList<int>>();
int total = 1 << n;
for (int mask = 0; mask < total; ++mask) {
if (CountBits(mask) == k) {
var current = new List<int>();
for (int i = 0; i < n; ++i) {
if ((mask & (1 << i)) != 0) {
current.Add(i + 1);
}
}
result.Add(current);
}
}
return result;
}
private int CountBits(int n) {
int count = 0;
while (n > 0) {
count += n & 1;
n >>= 1;
}
return count;
}
public static void Main(string[] args) {
var solution = new Solution();
var combinations = solution.Combine(4, 2);
foreach (var combo in combinations) {
Console.WriteLine("[{0}]", string.Join(", ", combo));
}
}
}Python treats masks as integers, transformed into binary strings to count ones with bin(mask).count('1'), filtering valid combinations by ensuring the bit count equals k.
Time Complexity: O(2n * n) due to masking through whole set.
Space Complexity: O(C(n, k) * k) for all valid combinations stored.
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
tequalsk, 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
ito the search patht, and then continue the search, i.e., executedfs(i + 1), and then remove the numberifrom the search patht; or we do not add the numberito the search patht, and directly executedfs(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:
function combine(n: number, k: number): number[][] {
const ans: number[][] = [];
const t: number[] = [];
const dfs = (i: number) => {
if (t.length === k) {
ans.push(t.slice());
return;
}
if (i > n) {
return;
}
t.push(i);
dfs(i + 1);
t.pop();
dfs(i + 1);
};
dfs(1);
return ans;
}func combine(n int, k int) (ans [][]int) {
t := []int{}
var dfs func(int)
dfs = func(i int) {
if len(t) == k {
ans = append(ans, slices.Clone(t))
return
}
if i > n {
return
}
t = append(t, i)
dfs(i + 1)
t = t[:len(t)-1]
dfs(i + 1)
}
dfs(1)
return
}impl Solution {
fn dfs(i: i32, n: i32, k: i32, t: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>) {
if t.len() == (k as usize) {
ans.push(t.clone());
return;
}
if i > n {
return;
}
t.push(i);
Self::dfs(i + 1, n, k, t, ans);
t.pop();
Self::dfs(i + 1, n, k, t, ans);
}
pub fn combine(n: i32, k: i32) -> Vec<Vec<i32>> {
let mut ans = vec![];
Self::dfs(1, n, k, &mut vec![], &mut ans);
ans
}
}Approach 4: Default Approach
function combine(n: number, k: number): number[][] {
const ans: number[][] = [];
const t: number[] = [];
const dfs = (i: number) => {
if (t.length === k) {
ans.push(t.slice());
return;
}
if (i > n) {
return;
}
for (let j = i; j <= n; ++j) {
t.push(j);
dfs(j + 1);
t.pop();
}
};
dfs(1);
return ans;
}func combine(n int, k int) (ans [][]int) {
t := []int{}
var dfs func(int)
dfs = func(i int) {
if len(t) == k {
ans = append(ans, slices.Clone(t))
return
}
if i > n {
return
}
for j := i; j <= n; j++ {
t = append(t, j)
dfs(j + 1)
t = t[:len(t)-1]
}
}
dfs(1)
return
}impl Solution {
fn dfs(i: i32, n: i32, k: i32, t: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>) {
if t.len() == (k as usize) {
ans.push(t.clone());
return;
}
if i > n {
return;
}
for j in i..=n {
t.push(j);
Self::dfs(j + 1, n, k, t, ans);
t.pop();
}
}
pub fn combine(n: i32, k: i32) -> Vec<Vec<i32>> {
let mut ans = vec![];
Self::dfs(1, n, k, &mut vec![], &mut ans);
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time Complexity: O(C(n, k) * k) since each combination is of size k. |
| Iterative Approach Using Bit Masking | Time Complexity: O(2n * n) due to masking through whole set. |
| Backtracking (Two Ways) | – |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking | O(C(n,k) * k) | O(k) | Best general solution. Generates only valid combinations and scales well for typical constraints. |
| Iterative Bit Masking | O(2^n * n) | O(k) | Useful when practicing subset enumeration or when n is small. |
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.