Log inSign up
mediumLeetCodeNot Started

Combinations

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Backtracking
Solve on LeetCode
Lesson

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 · Standard n = 4, k = 2:

Input: n = 4, k = 2
Output: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
Explanation: All 6 combinations of 2 numbers chosen from [1, 2, 3, 4].

Example 2 · Single Element Combination:

Input: n = 1, k = 1
Output: [[1]]
Explanation: Choosing 1 number from [1] yields [[1]].

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master lookahead upper-bound pruning in combinatorial loops.
  • Understand the mathematical difference between Permutations (order matters) and Combinations (order does not matter).
  • Derive the exact number of nodes visited in the combinatorial tree.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Generate all possible subsets of exact size k from range [1, n]
  • Combinations must be unique (order within combination does not matter)
  • Range elements are strictly distinct and sorted 1..n

Algorithmic Decision Tree:

  • Use Backtracking with state (start, current).
  • Loop i from start to n - (k - current.length) + 1.
  • Push i, recurse with start = i + 1, and pop i.

Connected Patterns:

SubsetsCombination Sum IIIPermutations

1. Binary Pick / Don't Pick Full Range Traversal

Intuition

Define solve(currNum, current). Base case: if current.length == k, add copy to result. If currNum > n, terminate. Recurse by either picking currNum or skipping currNum.

When to apply: Simple conceptual baseline.

Algorithm

  1. If current.length == k, add current to result and return.
  2. If currNum > n, return.
  3. Pick branch: current.push(currNum), solve(currNum + 1), current.pop().
  4. Don't pick branch: solve(currNum + 1).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7 void solve(int num, int n, int k, vector<int>& current, vector<vector<int>>& result) {
8 if (current.size() == k) {
9 result.push_back(current);
10 return;
11 }
12 if (num > n) return;
13
14 // Pick num
15 current.push_back(num);
16 solve(num + 1, n, k, current, result);
17 current.pop_back();
18
19 // Don't pick num
20 solve(num + 1, n, k, current, result);
21 }
22
23public:
24 vector<vector<int>> combine(int n, int k) {
25 vector<vector<int>> result;
26 vector<int> current;
27 solve(1, n, k, current, result);
28 return result;
29 }
30};
31
32int main() {
33 Solution sol;
34 auto res = sol.combine(4, 2);
35 for (const auto& c : res) {
36 cout << "[ ";
37 for (int v : c) cout << v << " ";
38 cout << "] ";
39 }
40 cout << endl;
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(2^n * k) — Generates up to 2n binary decisions across all numbers 1..n.
  • Space complexity: O(n) — Call stack reaches maximum depth n.

2. Standard Backtracking with Naive Loop (1..n)

Intuition

Loop i from start to n. In each iteration, push i, recurse with start = i + 1, and pop i. When current.length == k, add to result.

When to apply: Standard backtracking pattern without lookahead boundary calculation.

Algorithm

  1. If current.length == k, append copy of current to result and return.
  2. Loop i from start to n:
  3. - Push i to current.
  4. - Recurse backtrack(i + 1, current).
  5. - Pop i from current.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7 void backtrack(int start, int n, int k, vector<int>& current, vector<vector<int>>& result) {
8 if (current.size() == k) {
9 result.push_back(current);
10 return;
11 }
12
13 for (int i = start; i <= n; i++) {
14 current.push_back(i);
15 backtrack(i + 1, n, k, current, result);
16 current.pop_back();
17 }
18 }
19
20public:
21 vector<vector<int>> combine(int n, int k) {
22 vector<vector<int>> result;
23 vector<int> current;
24 backtrack(1, n, k, current, result);
25 return result;
26 }
27};
28
29int main() {
30 Solution sol;
31 auto res = sol.combine(4, 2);
32 for (const auto& c : res) {
33 cout << "[ ";
34 for (int v : c) cout << v << " ";
35 cout << "] ";
36 }
37 cout << endl;
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(C(n, k) * k) — Generates all C(n, k) combinations directly without permutation duplicates.
  • Space complexity: O(k) — Stack depth is bounded by k.

3. Backtracking with Lookahead Upper-Bound Pruning (Optimal)

Intuition

Suppose n = 4, k = 2. When current.size() == 0, we need 2 numbers. Starting at i = 4 leaves only [4] (1 number), which cannot possibly form size 2. The maximum valid starting index is n - (k - current.size()) + 1 = 4 - 2 + 1 = 3. Pruning dead branches up-front cuts out unnecessary recursive frames.

When to apply: The optimal, highly pruned interview standard for combinations.

Algorithm

  1. Define backtrack(start, current):
  2. - If current.length == k, append copy of current to result and return.
  3. - Calculate maxStart = n - (k - current.length) + 1.
  4. - Loop i from start to maxStart:
  5. - Push i to current.
  6. - Recurse backtrack(i + 1, current).
  7. - Pop i from current.
  8. Return result.

Lookahead Pruning Combinations Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Root state: k = 2, n = 4, maxStart = 4 - 2 + 1 = 3
Visual state
Values and pointers at this exact step
tree
Root
slots: 2, range: 1..4

Node order shown; add connections to display explicit tree edges.

Variables at this step
k
2
n
4
validStarts
[1,2,3]
Why this step matters

Root state: k = 2, n = 4, maxStart = 4 - 2 + 1 = 3. Candidates for first element: {1, 2, 3}.

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7 void backtrack(int start, int n, int k, vector<int>& current, vector<vector<int>>& result) {
8 if (current.size() == k) {
9 result.push_back(current);
10 return;
11 }
12
13 // Lookahead pruning: remaining slots needed = k - current.size()
14 // Upper bound for i = n - (k - current.size()) + 1
15 int maxStart = n - (k - current.size()) + 1;
16 for (int i = start; i <= maxStart; i++) {
17 current.push_back(i);
18 backtrack(i + 1, n, k, current, result);
19 current.pop_back(); // backtrack
20 }
21 }
22
23public:
24 vector<vector<int>> combine(int n, int k) {
25 vector<vector<int>> result;
26 vector<int> current;
27 backtrack(1, n, k, current, result);
28 return result;
29 }
30};
31
32int main() {
33 Solution sol;
34 auto res = sol.combine(4, 2);
35 for (const auto& c : res) {
36 cout << "[ ";
37 for (int v : c) cout << v << " ";
38 cout << "] ";
39 }
40 cout << endl;
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(C(n, k) * k) — Generates exactly C(n, k) combination paths without visiting dead-end states.
  • Space complexity: O(k) — Auxiliary space is bounded by the recursion depth k.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Binary Pick / Don't Pick Full RangeO(2^n * k)O(n)Binary decisions for each integer 1..n.Binary tree call frames
2.Standard Backtracking with Naive LoopO(C(n, k) * k)O(k)Loop start..n to choose elements in strictly increasing order.Extra recursive base-case checks
3.Backtracking with Lookahead Upper-Bound PruningOptimalO(C(n, k) * k)O(k)Bound loop by n - (k - size) + 1 to guarantee sufficient remaining elements.Combination generation count

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Using i = 1 instead of i = start in the loop (which would generate permutations with duplicates like [2, 1]).

Pitfall 2:

Off-by-one error in maxStart = n - (k - current.length) + 1 (forgetting the + 1).

Pitfall 3:

Forgetting to make a shallow copy of current before adding to result.

Crucial Edge Cases to Validate:

  • k = 1: n = 4, k = 1 -> returns [[1], [2], [3], [4]].
  • k = n: n = 3, k = 3 -> returns [[1, 2, 3]].
  • Single Element: n = 1, k = 1 -> returns [[1]].

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always derive the lookahead formula maxStart = n - (k - size) + 1 aloud for the interviewer to show mathematical depth.
  2. Contrast Combinations with Permutations and Subsets.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.For n = 5 and k = 3, what is the maximum starting number for the first element?

2.How many total combinations are generated for n = 4 and k = 2?

Back to DSA Sheet