Jobs

Interviews

Discussions

Subsets

Medium

Subsets

Medium

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 is the maximum size of the input array `nums`? Is there a memory constraint to consider?
Can the input array `nums` contain negative numbers or zero?
Although the problem states 'unique integers', I want to confirm: are we absolutely guaranteed that there will be no duplicate integers in the `nums` array?
Is there a specific order required for the subsets in the output list, or for the elements within each subset?
Should the empty set (the subset with no elements) be included in the output?

Brute Force Solution

Approach

The brute force method for finding all subsets means we're going to explore absolutely every possibility. We consider each item and decide whether to include it or not, building every combination imaginable. This guarantees we don't miss any subset.

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

Start with an empty set, which is always a subset.
Look at the first item in your original set.
Create a new set that includes only the first item. This is a new subset.
Now, look at the second item.
Generate new subsets by adding the second item to each of the subsets you already have (the empty set and the set with the first item).
Repeat this process for every item in the original set.
Each time, you create new subsets by taking all the subsets you've found so far and adding the current item to each of them.
At the end, you'll have a list of all possible subsets, including the empty set and the original set itself.

Code Implementation

def find_all_subsets(original_set):
    list_of_all_subsets = [[]]

    for current_element in original_set:
        # Create a new list to hold the new subsets.

        new_subsets = []

        for existing_subset in list_of_all_subsets:
            # Create a new subset by adding the current element to the existing subset.
            new_subset = existing_subset + [current_element]

            # Add the new subset to the list of new subsets.
            new_subsets.append(new_subset)

        # Add all the new subsets to the list of all subsets.
        # This is needed to account for all possible combinations. 
        list_of_all_subsets.extend(new_subsets)

    # Return the final list of all subsets
    return list_of_all_subsets

Big(O) Analysis

Time Complexity

O(2^n) – The algorithm iterates through each element of the input array of size n. For each element, it effectively doubles the number of subsets accumulated so far. Starting with one empty subset, after considering the first element, we have two subsets. After the second, four, and so on. This doubling process for each of the n elements leads to 2^n subsets. Hence, the time complexity is O(2^n).

Space Complexity

O(2^N) – The algorithm generates all possible subsets of the input set. Each subset requires storing its elements, and in the worst case, there are 2^N subsets for an input set of size N. Therefore, the space required to store all these subsets grows exponentially with the input size. The list of subsets being constructed to store these subsets is the dominant auxiliary space consumer, using space proportional to the total number of subsets. This leads to a space complexity of O(2^N).

Optimal Solution

Approach

The idea is to systematically build all possible groups, one element at a time. For each number, we decide whether to include it in our existing groups or not, effectively doubling the number of groups we have at each step. This allows us to generate all subsets in a structured manner.

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

Start with an empty set, which is always a subset of any set.
Consider the first number. We now have two choices: either include it in the existing subset (the empty set), or don't.
This creates a new subset containing just the first number, in addition to the original empty set.
Move to the second number. Again, for each existing subset (empty set and the set containing the first number), we decide whether to include the second number or not.
If we include it, we add the second number to each of the existing subsets, creating two new subsets.
If we don't include it, we keep the existing subsets as they are.
Continue this process for each number in the original set. At each step, we take all previously generated subsets and create new ones by adding the current number to each of them.
After processing all numbers, we will have a list of all possible subsets of the original set.

Code Implementation

def get_all_subsets(input_set):
    all_subsets = [[]]

    for number in input_set:
        # Iterate through existing subsets to extend them.

        new_subsets = []
        for existing_subset in all_subsets:
            # Create a new subset by adding the current number.

            new_subset = existing_subset + [number]
            new_subsets.append(new_subset)

        # Add all the new subsets created in the inner loop.
        all_subsets.extend(new_subsets)

    return all_subsets

Big(O) Analysis

Time Complexity

O(n*2^n) – The algorithm iterates through each of the n elements in the input array. For each element, it effectively doubles the number of subsets generated so far. Starting with a single empty set, each element has the potential to create a new subset from each existing subset. Therefore, the number of subsets grows exponentially, resulting in 2^n total subsets. Since constructing each of these subsets might require copying up to n elements, the overall time complexity becomes O(n*2^n).

Space Complexity

O(2^N) – The algorithm generates all possible subsets. In the worst case, a set with N elements has 2^N subsets. The algorithm stores all these subsets in a list or similar data structure to hold the results, requiring space proportional to the number of subsets. Therefore, the auxiliary space required is dominated by the storage of the 2^N subsets. This leads to a space complexity of O(2^N), where N is the number of elements in the input set.

Edge Cases

Case	How to Handle
Null or empty input array	Return a list containing only an empty set.
Input array with a single element	Return a list containing the empty set and the set with that single element.
Large input array (e.g., nums.length > 20)	Consider the exponential time complexity (O(2^n)) and potential for performance issues, and use bit manipulation for efficiency.
Input array contains negative numbers	The algorithm should handle negative numbers without any issues as it operates on the presence/absence of elements, not their values.
Input array contains zero	Zero should be treated like any other unique integer in the array, and the algorithm should correctly generate subsets including and excluding zero.
Maximum-sized integers in the input array (Integer.MAX_VALUE)	Integer overflow is not relevant for subset generation since we're not performing arithmetic operations on the values themselves; the algorithm focuses on element inclusion.
Duplicate numbers in the input array (violates problem statement)	Since the problem statement specifies unique integers, if duplicates are present, preprocessing might be needed to remove duplicates, or the algorithm needs to be adjusted to prevent duplicate subsets (e.g., by sorting the input and skipping duplicate elements during recursion).
Extreme boundary values (Integer.MIN_VALUE, Integer.MAX_VALUE)	Ensure these boundary values are handled without causing issues during any internal calculations, comparisons, or data structure operations; the subset generation itself shouldn't be affected.

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 is the maximum size of the input array `nums`? Is there a memory constraint to consider?
Can the input array `nums` contain negative numbers or zero?
Although the problem states 'unique integers', I want to confirm: are we absolutely guaranteed that there will be no duplicate integers in the `nums` array?
Is there a specific order required for the subsets in the output list, or for the elements within each subset?
Should the empty set (the subset with no elements) be included in the output?

Brute Force Solution

Approach

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

Start with an empty set, which is always a subset.
Look at the first item in your original set.
Create a new set that includes only the first item. This is a new subset.
Now, look at the second item.
Generate new subsets by adding the second item to each of the subsets you already have (the empty set and the set with the first item).
Repeat this process for every item in the original set.
Each time, you create new subsets by taking all the subsets you've found so far and adding the current item to each of them.
At the end, you'll have a list of all possible subsets, including the empty set and the original set itself.

Code Implementation

def find_all_subsets(original_set):
    list_of_all_subsets = [[]]

    for current_element in original_set:
        # Create a new list to hold the new subsets.

        new_subsets = []

        for existing_subset in list_of_all_subsets:
            # Create a new subset by adding the current element to the existing subset.
            new_subset = existing_subset + [current_element]

            # Add the new subset to the list of new subsets.
            new_subsets.append(new_subset)

        # Add all the new subsets to the list of all subsets.
        # This is needed to account for all possible combinations. 
        list_of_all_subsets.extend(new_subsets)

    # Return the final list of all subsets
    return list_of_all_subsets

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start with an empty set, which is always a subset of any set.
Consider the first number. We now have two choices: either include it in the existing subset (the empty set), or don't.
This creates a new subset containing just the first number, in addition to the original empty set.
Move to the second number. Again, for each existing subset (empty set and the set containing the first number), we decide whether to include the second number or not.
If we include it, we add the second number to each of the existing subsets, creating two new subsets.
If we don't include it, we keep the existing subsets as they are.
Continue this process for each number in the original set. At each step, we take all previously generated subsets and create new ones by adding the current number to each of them.
After processing all numbers, we will have a list of all possible subsets of the original set.

Code Implementation

def get_all_subsets(input_set):
    all_subsets = [[]]

    for number in input_set:
        # Iterate through existing subsets to extend them.

        new_subsets = []
        for existing_subset in all_subsets:
            # Create a new subset by adding the current number.

            new_subset = existing_subset + [number]
            new_subsets.append(new_subset)

        # Add all the new subsets created in the inner loop.
        all_subsets.extend(new_subsets)

    return all_subsets

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return a list containing only an empty set.
Input array with a single element	Return a list containing the empty set and the set with that single element.
Large input array (e.g., nums.length > 20)	Consider the exponential time complexity (O(2^n)) and potential for performance issues, and use bit manipulation for efficiency.
Input array contains negative numbers	The algorithm should handle negative numbers without any issues as it operates on the presence/absence of elements, not their values.
Input array contains zero	Zero should be treated like any other unique integer in the array, and the algorithm should correctly generate subsets including and excluding zero.
Maximum-sized integers in the input array (Integer.MAX_VALUE)	Integer overflow is not relevant for subset generation since we're not performing arithmetic operations on the values themselves; the algorithm focuses on element inclusion.
Duplicate numbers in the input array (violates problem statement)	Since the problem statement specifies unique integers, if duplicates are present, preprocessing might be needed to remove duplicates, or the algorithm needs to be adjusted to prevent duplicate subsets (e.g., by sorting the input and skipping duplicate elements during recursion).
Extreme boundary values (Integer.MIN_VALUE, Integer.MAX_VALUE)	Ensure these boundary values are handled without causing issues during any internal calculations, comparisons, or data structure operations; the subset generation itself shouldn't be affected.