77. Combinations

Problem Description

The problem requires us to generate all combinations of k numbers from a set of integers ranging from 1 to n. A combination is a selection of items from a collection, such that the order of selection does not matter. In mathematical terms, you are asked to find all possible subsets of size k from the given range.

For instance, if n=4 and k=2, the function should return combinations like [1,2], [1,3], [1,4], [2,3], [2,4] and [3,4]. Importantly, combinations do not account for order; thus, [1,2] is considered the same as [2,1] and should not be listed as a separate combination.

The answer can be returned in any sequence, meaning the combinations do not need to be sorted in any particular order.

Intuition

To solve this problem, we use a method called depth-first search (DFS), which is commonly used to traverse or search tree or graph data structures. The concept can also be applied to recursively generate combinations.

Here's how we can think through the DFS approach:

Imagine each number i in the range [1, n] is a potential candidate to be included in a combination. For each candidate, we have two choices: either include it in the current combination t or skip it and move on to the next number without adding it.
Starting from the first number, we dive deeper by making a recursive call with that number included in our current combination. This is the "depth-first" part where we are trying to build a complete combination by adding one number at a time.
Once we hit a base case where the combination has a length of k, we've found a valid combination and add a copy of it to our answer list ans. We must remember to add a copy (t[:]) because t will continue to be modified.
After exploring the depth with the current number included, we backtrack by removing the last included number (t.pop()) and proceed to the next recursive call without the current number, effectively exploring the possibility where the current number is not part of the combination.
The process continues until all combinations of size k have been added to the answer list, involving exploring each number's inclusion and exclusion systematically.

By using the DFS pattern, we ensure all possible combinations are accounted for, by systematically including and excluding each number, and exploring combinations further only until they've reached the desired size k.

This is an elegant solution to the problem because it inherently handles the constraint that combinations must be of size k, and it requires no special handling to avoid duplicate combinations (since we only ever move forward to higher numbers, never backwards).

Learn more about Backtracking patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

[1, 2, 3, 4, 5][1, 3, 6, 10, 15][15, 14, 12, 9, 5][5, 4, 3, 2, 1]

I don’t know

Solution Approach

The solution uses DFS, a common algorithm for traversing or searching through a tree or graph structure, to explore all combinations of k numbers from range [1, n].

Here’s the step-by-step breakdown of how the code implements this approach:

Define a helper function dfs with a parameter i, which represents the current number being considered to be part of a combination.
Use a list t to store the current state of the combination being built.
If the length of t matches k, a complete combination has been formed. Make a copy of t using slicing (t[:]) and append it to our answer list ans.
If i goes beyond n, it means we've considered all possible numbers and should terminate this path of the DFS.
For the current number i, add it to the combination list t and call dfs(i + 1) to consider the next number, diving deeper into the DFS path.
After exploring the path with number i included, backtrack by removing i from t using t.pop() to undo the previous action.
Call dfs(i + 1) again to explore the path where i is not included in the combination.
Initialize the answer list ans and the temporary combination list t outside the helper function.
Start the DFS by calling dfs(1), which will traverse all paths and fill ans with all possible combinations.
Once the DFS is complete, return the ans list, which contains the desired combinations.

The choice of data structures is straightforward. A list is used to keep track of the current combination (t) and the final list of combinations (ans). The use of list operations like append() to add to a combination and pop() to remove from it, enable efficient manipulation of the temporary combination while it's being built.

The DFS algorithm elegantly handles both the generation of combinations and the adherence to the constraint of each combination having size k, without the need for explicit checks to avoid duplicates or additional data structures.

The code leverages recursion to simplify the logic. It systematically includes each eligible number into a combination, recurses to consider additional numbers, then backtracks to exclude the number and recurse again. This ensures we explore all combinations of numbers from [1, n] of size k.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Example Walkthrough

Let's take n = 3 and k = 2 as a simple example to walk through the solution approach described above. Our aim is to generate all combinations where the size of each combination (k) is 2, using integers from 1 to 3.

Here's how we would execute the described algorithm step-by-step:

We start by initializing the answer list ans to hold our final combinations, and a temporary list t to hold the current combination we are building.
We begin our DFS traversal by invoking dfs(1). This signals that we will start looking for combinations beginning with the number 1.
The first call to dfs looks at number 1 (i = 1). Since our t list is empty, and we haven't reached a combination of length k yet, we add 1 to t.
Next, we make a recursive call to dfs(2), indicating that we should now consider number 2 for inclusion in the combination. Our t list currently is [1].
In the dfs(2) call, we see that t still hasn't reached the length k, so we add 2 to t, which now becomes [1, 2].
Upon the next invocation dfs(3), the length of t is indeed k, so we add a copy of t to ans. ans now contains [[1, 2]].
We backtrack by popping number 2 from t, then proceed by calling dfs(3) to consider combinations starting with [1] again but excluding the number 2 this time.
Since number 3 is within our range, we add it to t which becomes [1, 3]. That's another valid combination of length k, so we add a copy to ans. Now ans becomes [[1, 2], [1, 3]].
We backtrack again, removing the number 3 from t and since there are no more numbers to consider after 3, the function rolls back to the previous stack frame where i was 2.
Now, we are back to dfs(2), but since we've exhausted possibilities for the number 2, we increment to dfs(3) where we try to include the number 3 in the combination. Since 2 was already considered, our t list is empty at this point, so we add 3 to t to make [3].
Calling dfs(4) from here we find that there are no more numbers to combine with 3 without consideration of the number 2 (which was already part of a previous combination), and since for this step i has exceeded n, no further action is taken and we revert back to the moment before including 3.
At this point, we have explored and returned from all possible DFS paths for the number 1. Now we increment to considering dfs(2). Following the same procedure, we find the combination [2, 3] which is added to ans.
After exhausting all possible recursive paths, our DFS traversal is complete. Our final ans list, which contains all possible combinations, is [[1, 2], [1, 3], [2, 3]].
We return ans, which is the output of our function.

We have now successfully generated all combinations of k numbers from a set of integers ranging from 1 to n. The elegance of this approach lies in its methodical inclusion and exclusion of each integer, ensuring all unique combinations are found, while the recursive structure keeps the code simple and concise.

Solution Implementation

1class Solution:
2    def combine(self, n: int, k: int) -> List[List[int]]:
3        # Helper function for the depth-first search algorithm.
4        def dfs(start: int):
5            # If the current combination size equals k, save a copy to the answer list.
6            if len(current_combination) == k:
7                combinations.append(current_combination[:])
8                return
9            # If the current start exceeds n, stop exploring this path.
10            if start > n:
11                return
12            # Include the current number in the combination and move to the next.
13            current_combination.append(start)
14            dfs(start + 1)
15            # Exclude the current number from the combination and move to the next.
16            current_combination.pop()
17            dfs(start + 1)
18
19        # Initialize the list to store all possible combinations.
20        combinations = []
21        # List to store the current combination of numbers.
22        current_combination = []
23        # Start DFS with the smallest possible number.
24        dfs(1)
25        # Return all the possible combinations found.
26        return combinations
27

1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5    private final List<List<Integer>> combinations = new ArrayList<>();
6    private final List<Integer> currentCombination = new ArrayList<>();
7    private int totalNumbers;
8    private int combinationSize;
9
10    // Generates all combinations of numbers of size k from a set of numbers from 1 to n.
11    public List<List<Integer>> combine(int n, int k) {
12        totalNumbers = n;
13        combinationSize = k;
14        backtrack(1); // Start the backtracking algorithm from the first element
15        return combinations;
16    }
17
18    // Uses backtracking to find all combinations.
19    private void backtrack(int startIndex) {
20        // If the current combination's size is equal to the desired size,
21        // add it to the list of combinations.
22        if (currentCombination.size() == combinationSize) {
23            combinations.add(new ArrayList<>(currentCombination));
24            return;
25        }
26      
27        // If the index has gone beyond the last number, end the current path.
28        if (startIndex > totalNumbers) {
29            return;
30        }
31      
32        // Include the current number in the combination and move to the next number.
33        currentCombination.add(startIndex);
34        backtrack(startIndex + 1);
35
36        // Exclude the current number from the combination and move to the next number.
37        currentCombination.remove(currentCombination.size() - 1);
38        backtrack(startIndex + 1);
39    }
40}
41

1#include <vector>
2#include <functional> // For std::function
3
4class Solution {
5public:
6    // Returns all possible combinations of k numbers out of 1...n
7    vector<vector<int>> combine(int n, int k) {
8        vector<vector<int>> combinations; // Stores all the combinations
9        vector<int> current; // Stores the current combination
10
11        // Depth-first search (DFS) to find all combinations
12        std::function<void(int)> dfs = [&](int start) {
13            // If the current combination is of size k, add it to the answers
14            if (current.size() == k) {
15                combinations.emplace_back(current);
16                return;
17            }
18
19            // If we've passed the last number, stop the recursion
20            if (start > n) {
21                return;
22            }
23
24            // Include the current number and go deeper
25            current.emplace_back(start);
26            dfs(start + 1); // Recurse with the next number
27
28            // Exclude the current number and go deeper
29            current.pop_back();
30            dfs(start + 1); // Recurse with the next number
31        };
32
33        // Start the recursion with the first number
34        dfs(1);
35
36        // Return all the found combinations
37        return combinations;
38    }
39};
40

1// Function to generate all possible combinations of k numbers out of the range [1, n].
2function combine(n: number, k: number): number[][] {
3    // Initialize the array to hold the resulting combinations.
4    const combinations: number[][] = [];
5    // Temporary array to hold the current combination.
6    const currentCombination: number[] = [];
7    // Depth-first search function to explore all possible combinations.
8    const depthFirstSearch = (currentIndex: number) => {
9        // If the current combination's length is k, a complete combination has been found.
10        if (currentCombination.length === k) {
11            // Add a copy of the current combination to the results.
12            combinations.push(currentCombination.slice());
13            return;
14        }
15        // If the currentIndex exceeds n, we've explored all numbers, so return.
16        if (currentIndex > n) {
17            return;
18        }
19        // Include the current index in the current combination and move to the next number.
20        currentCombination.push(currentIndex);
21        depthFirstSearch(currentIndex + 1);
22        // Exclude the current index from the current combination and move to the next number.
23        currentCombination.pop();
24        depthFirstSearch(currentIndex + 1);
25    };
26    // Start the depth-first search from number 1.
27    depthFirstSearch(1);
28    // Return all the generated combinations.
29    return combinations;
30}
31

Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10][100, 33, 30][10, 12, 20]

I don’t know

Time and Space Complexity

The provided Python code performs combinations of n numbers taken k at a time. It uses a depth-first search (DFS) recursive strategy to generate all possible combinations.

Time Complexity

The time complexity of this algorithm can be determined by considering the number of recursive calls. At each point, the function has the choice to include a number in the combination or to move past it without including it. This results in the algorithm having a binary choice for each of the n numbers, which hints at a O(2^n) time complexity.

However, due to the nature of combinations, the recursive calls early terminate when the length of the temporary list t equals k. Therefore, the time complexity is better approximated by the number of k-combinations of n, which is O(n choose k). Using binomial coefficient, the time complexity can be expressed as O(n! / (k! * (n - k)!)).

Space Complexity

The space complexity includes the space for the output list and the space used by the call stack due to recursion.

Output List: The output list will hold C(n, k) combinations, and each combination is a list of k elements. Therefore, the space needed for the output list is O(n choose k * k).
Recursion Stack: The maximum depth of the recursion is n because in the worst case, the algorithm would go as deep as trying to decide whether to include the last number. Therefore, the space used by the call stack is O(n).

When considering space complexity, it is important to recognize that the complexity depends on the maximum space usage at any time. So, the space complexity of the DFS recursive solution is dominated by the space needed for the output list. Hence, the space complexity is O(n choose k * k).

In summary:

The time complexity is O(n! / (k! * (n - k)!)).
The space complexity is O(n choose k * k).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Depth first search can be used to find whether two components in a graph are connected.

TrueFalse

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

77. Combinations

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings