Jobs

Interviews

Discussions

Combinations

Medium

Asked by:

More companies

133 views

Topics:

Recursion

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

Try coding it in LeetCode

Combinations

Medium

Asked by:

133 views

Topics:

Recursion

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on n and k? Specifically, what are the maximum and minimum values for n and k, and is k guaranteed to be less than or equal to n?
If n is zero or k is zero, or if k is greater than n, what should I return? Should I return an empty list?
Is the order of combinations in the output list important? Is there a specific order that is preferred (e.g., lexicographical order)?
Within each combination, is the order of the numbers important? Should each combination be sorted in ascending order?
Can I modify the input values n and k, or should I treat them as read-only?

Brute Force Solution

Approach

The brute force approach to finding combinations is like trying every single possible group. We build up combinations one element at a time, considering all options at each step, until we've exhausted all possibilities.

Here's how the algorithm would work step-by-step:

Start with an empty group.
Consider the first item. Either include it in the group or leave it out, creating two new groups.
For each of those new groups, consider the next item. Again, either include it or leave it out, doubling the number of groups again.
Keep doing this for every item in the list. At each step, every group splits into two: one with the current item and one without.
Once you've considered all the items, you'll have a collection of every possible group.
Finally, filter this collection to keep only the groups of the correct size.

Code Implementation

def combinations_brute_force(elements, combination_length):
    all_possible_combinations = [[]] 

    for element in elements:
        new_combinations = []
        for current_combination in all_possible_combinations:
            # Create a new combination with the current element
            new_combinations.append(current_combination + [element])

            # Keep the existing combination without the current element
            new_combinations.append(current_combination)

        all_possible_combinations = new_combinations

    # Filter to keep only combinations of the specified length
    final_combinations = []
    for combination in all_possible_combinations:
        if len(combination) == combination_length:
            final_combinations.append(combination)

    return final_combinations

Big(O) Analysis

Time Complexity

O(2^n) – The algorithm explores all possible combinations by making a choice for each element: either include it or exclude it. This binary decision for each of the n elements results in 2^n possible combinations being generated. After generating all combinations, the algorithm filters the results, which takes O(2^n) in the worst case if we have to examine all the 2^n generated lists. Therefore, the overall time complexity is dominated by the generation of all subsets which is O(2^n).

Space Complexity

O(2^N) – The algorithm builds up combinations by considering each item and either including it or excluding it in the current group. This process effectively doubles the number of groups at each step. Since we do this for every item in the list of size N, the number of groups can grow up to 2^N in the worst case. We need to store each of these groups, leading to an auxiliary space requirement of O(2^N).

Optimal Solution

Approach

The best way to find all possible combinations is to build them step-by-step, making sure we only add valid elements. We use a special technique called backtracking, which is like exploring a maze where we try different paths, and if a path doesn't work, we go back and try another one.

Here's how the algorithm would work step-by-step:

Start with an empty combination.
Add the smallest available number to the combination.
If the combination is now the right size, save it as a valid result.
If the combination is not yet the right size, repeat the process: add another number that is larger than the last one added, and continue until the combination is full or no valid numbers remain.
If at any point you can't add another number because you've reached the maximum number or the combination is full, go back and remove the last number you added.
Then, try adding the next largest valid number from where you left off. This is the 'backtracking' step.
Continue this process of adding, saving (if complete), and backtracking until you've explored all possible paths and found every valid combination.

Code Implementation

def combinations(n, k):
    result = []
    current_combination = []

    def backtrack(start_number):
        # If combination is the correct size, add it to results
        if len(current_combination) == k:
            result.append(current_combination[:])
            return

        # Iterate through possible numbers to add to combination
        for number in range(start_number, n + 1):
            current_combination.append(number)

            # Recursive call to continue building the combination
            backtrack(number + 1)

            # Backtrack: Remove the last added number to explore other options
            current_combination.pop()

    backtrack(1)
    return result

Big(O) Analysis

Time Complexity

O(C(n, k)) – The algorithm explores all possible combinations of k elements chosen from a set of n elements. The number of such combinations is given by the binomial coefficient C(n, k), which is n! / (k! * (n-k)!). While the backtracking process explores a tree-like structure, the number of leaf nodes (valid combinations) directly corresponds to C(n, k). The time complexity is therefore proportional to the number of combinations generated. Thus, the runtime is O(C(n, k)).

Space Complexity

O(k) – The space complexity is dominated by the 'combination' list which stores the current combination being built. In the worst case, this list can grow up to size k, where k is the desired size of each combination. The recursion stack also contributes to the space complexity, with a maximum depth of n (where n is the range of numbers to choose from), but since k is generally less than or equal to n, the 'combination' list is the dominant factor. Therefore, the auxiliary space is O(k).

Edge Cases

Case	How to Handle
n is 0 or negative	Return an empty list because no combinations can be formed from an empty or invalid range.
k is 0	Return an empty list because a combination of size 0 is typically considered to be the empty set, and we want a list of combinations.
k is greater than n	Return an empty list because it's impossible to choose k items from a range of size n if k > n.
n is a large number	Ensure the algorithm is efficient and doesn't lead to excessive recursion depth or memory usage that can cause stack overflow errors or out-of-memory issues.
k is equal to n	Return a list containing only one combination, which is the range [1, n].
k is equal to 1	Return a list of combinations, where each combination contains only one number from the range [1, n].
n is 1 and k is 1	Return a list containing one combination which is a list containing the number 1.
Integer overflow if n or k is very large	Use appropriate data types to prevent integer overflow when performing calculations involving n and k.

n is 0 or negative

How to Handle:

Return an empty list because no combinations can be formed from an empty or invalid range.

k is 0

How to Handle:

Return an empty list because a combination of size 0 is typically considered to be the empty set, and we want a list of combinations.

k is greater than n

How to Handle:

Return an empty list because it's impossible to choose k items from a range of size n if k > n.

n is a large number

How to Handle:

Ensure the algorithm is efficient and doesn't lead to excessive recursion depth or memory usage that can cause stack overflow errors or out-of-memory issues.

k is equal to n

How to Handle:

Return a list containing only one combination, which is the range [1, n].

k is equal to 1

How to Handle:

Return a list of combinations, where each combination contains only one number from the range [1, n].

n is 1 and k is 1

How to Handle:

Return a list containing one combination which is a list containing the number 1.

Integer overflow if n or k is very large

How to Handle:

Use appropriate data types to prevent integer overflow when performing calculations involving n and k.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on n and k? Specifically, what are the maximum and minimum values for n and k, and is k guaranteed to be less than or equal to n?
If n is zero or k is zero, or if k is greater than n, what should I return? Should I return an empty list?
Is the order of combinations in the output list important? Is there a specific order that is preferred (e.g., lexicographical order)?
Within each combination, is the order of the numbers important? Should each combination be sorted in ascending order?
Can I modify the input values n and k, or should I treat them as read-only?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with an empty group.
Consider the first item. Either include it in the group or leave it out, creating two new groups.
For each of those new groups, consider the next item. Again, either include it or leave it out, doubling the number of groups again.
Keep doing this for every item in the list. At each step, every group splits into two: one with the current item and one without.
Once you've considered all the items, you'll have a collection of every possible group.
Finally, filter this collection to keep only the groups of the correct size.

Code Implementation

def combinations_brute_force(elements, combination_length):
    all_possible_combinations = [[]] 

    for element in elements:
        new_combinations = []
        for current_combination in all_possible_combinations:
            # Create a new combination with the current element
            new_combinations.append(current_combination + [element])

            # Keep the existing combination without the current element
            new_combinations.append(current_combination)

        all_possible_combinations = new_combinations

    # Filter to keep only combinations of the specified length
    final_combinations = []
    for combination in all_possible_combinations:
        if len(combination) == combination_length:
            final_combinations.append(combination)

    return final_combinations

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start with an empty combination.
Add the smallest available number to the combination.
If the combination is now the right size, save it as a valid result.
If the combination is not yet the right size, repeat the process: add another number that is larger than the last one added, and continue until the combination is full or no valid numbers remain.
If at any point you can't add another number because you've reached the maximum number or the combination is full, go back and remove the last number you added.
Then, try adding the next largest valid number from where you left off. This is the 'backtracking' step.
Continue this process of adding, saving (if complete), and backtracking until you've explored all possible paths and found every valid combination.

Code Implementation

def combinations(n, k):
    result = []
    current_combination = []

    def backtrack(start_number):
        # If combination is the correct size, add it to results
        if len(current_combination) == k:
            result.append(current_combination[:])
            return

        # Iterate through possible numbers to add to combination
        for number in range(start_number, n + 1):
            current_combination.append(number)

            # Recursive call to continue building the combination
            backtrack(number + 1)

            # Backtrack: Remove the last added number to explore other options
            current_combination.pop()

    backtrack(1)
    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n is 0 or negative	Return an empty list because no combinations can be formed from an empty or invalid range.
k is 0	Return an empty list because a combination of size 0 is typically considered to be the empty set, and we want a list of combinations.
k is greater than n	Return an empty list because it's impossible to choose k items from a range of size n if k > n.
n is a large number	Ensure the algorithm is efficient and doesn't lead to excessive recursion depth or memory usage that can cause stack overflow errors or out-of-memory issues.
k is equal to n	Return a list containing only one combination, which is the range [1, n].
k is equal to 1	Return a list of combinations, where each combination contains only one number from the range [1, n].
n is 1 and k is 1	Return a list containing one combination which is a list containing the number 1.
Integer overflow if n or k is very large	Use appropriate data types to prevent integer overflow when performing calculations involving n and k.

n is 0 or negative

How to Handle:

Return an empty list because no combinations can be formed from an empty or invalid range.

k is 0

How to Handle:

Return an empty list because a combination of size 0 is typically considered to be the empty set, and we want a list of combinations.

k is greater than n

How to Handle:

Return an empty list because it's impossible to choose k items from a range of size n if k > n.

n is a large number

How to Handle:

Ensure the algorithm is efficient and doesn't lead to excessive recursion depth or memory usage that can cause stack overflow errors or out-of-memory issues.

k is equal to n

How to Handle:

Return a list containing only one combination, which is the range [1, n].

k is equal to 1

How to Handle:

Return a list of combinations, where each combination contains only one number from the range [1, n].

n is 1 and k is 1

How to Handle:

Return a list containing one combination which is a list containing the number 1.

Integer overflow if n or k is very large

How to Handle:

Use appropriate data types to prevent integer overflow when performing calculations involving n and k.