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.
Flowchart Walkthrough
Let's analyze LeetCode 77 "Combinations" using the Flowchart. Here's a step-by-step walkthrough to determine the appropriate algorithm:
Is it a graph?
- No: The problem does not involve nodes and edges as in graph theory but requires generating combinations.
Need to solve for kth smallest/largest?
- No: The task is about generating specific combinations, not finding a kth element.
Involves Linked Lists?
- No: The problem deals with numbers and combinations, not linked list structures.
Does the problem have small constraints?
- Yes: Combinations provides the ability to control over the values
n
andk
, suggesting manageable constraints for complete search strategies. In problems of this nature, enumerating possible combinations is feasible.
Brute force / Backtracking?
- Yes: Brute force or backtracking is needed as the problem requires exploring all combinations (
k
selections fromn
items) comprehensively.
Conclusion: The flowchart indicates that a Backtracking approach is ideal for systematically exploring and generating all combinations of the array as specified in the prompt for LeetCode 77. The algorithm can efficiently explore all possible combinations within permissible constraints through recursive exploration.
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 combinationt
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 listans
. We must remember to add a copy (t[:]
) becauset
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.
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 parameteri
, 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
matchesk
, a complete combination has been formed. Make a copy oft
using slicing (t[:]
) and append it to our answer listans
. -
If
i
goes beyondn
, 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 listt
and calldfs(i + 1)
to consider the next number, diving deeper into the DFS path. -
After exploring the path with number
i
included, backtrack by removingi
fromt
usingt.pop()
to undo the previous action. -
Call
dfs(i + 1)
again to explore the path wherei
is not included in the combination. -
Initialize the answer list
ans
and the temporary combination listt
outside the helper function. -
Start the DFS by calling
dfs(1)
, which will traverse all paths and fillans
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
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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 listt
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 ourt
list is empty, and we haven't reached a combination of lengthk
yet, we add 1 tot
. -
Next, we make a recursive call to
dfs(2)
, indicating that we should now consider number 2 for inclusion in the combination. Ourt
list currently is[1]
. -
In the
dfs(2)
call, we see thatt
still hasn't reached the lengthk
, so we add 2 tot
, which now becomes[1, 2]
. -
Upon the next invocation
dfs(3)
, the length oft
is indeedk
, so we add a copy oft
toans
.ans
now contains[[1, 2]]
. -
We backtrack by popping number 2 from
t
, then proceed by callingdfs(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 lengthk
, so we add a copy toans
. Nowans
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 wherei
was 2. -
Now, we are back to
dfs(2)
, but since we've exhausted possibilities for the number 2, we increment todfs(3)
where we try to include the number 3 in the combination. Since 2 was already considered, ourt
list is empty at this point, so we add 3 tot
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 stepi
has exceededn
, 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 toans
. -
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
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 ofk
elements. Therefore, the space needed for the output list isO(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 isO(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.
Which of these pictures shows the visit order of a depth-first search?
Recommended Readings
Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.