Subsets

Updated on 02 July, 2025
Subsets header image

Problem Statement

The objective is to generate all possible subsets of a given array, where the array contains unique integers. These subsets form what is known as the power set. Each subset can include any combination of the elements, from no element to all elements, without repeating any specific subset in the result. Since the elements are distinct, the subsets will naturally be unique. The outcome does not need to follow a specific order, and the primary condition is just to ensure that no two subsets are identical.

Examples

Example 1

Input:

nums = [1,2,3]

Output:

[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2

Input:

nums = [0]

Output:

[[],[0]]

Constraints

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • All the numbers of nums are unique.

Approach and Intuition

To tackle the problem of generating all subsets (power set) from a given unique list of integers, we can proceed with a systematic method:

  1. Understand that a power set of a set with n elements contains 2^n subsets, including the empty set and the set itself.

  2. Use a recursive or iterative method to generate these subsets. Each element in the input set has two choices: either it is included in a current subset or it is not.

  3. Example walk-through:

    • For example, consider nums = [1,2,3].
      • Start with an empty subset: [].
      • Add each element, branching at each step to explore both including and not including the next element.
      • For number 1, you get [] and [1].
      • For number 2, expand previous subsets to [], [1], [2], and [1,2].
      • For number 3, expand further to [], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3].
  4. Each step essentially builds upon the previous subsets forming a tree-like structure where at each node you decide "include" or "not include".

  5. Output all collected subsets once all elements have been processed, ensuring no duplicates since the input elements and processing guarantee uniqueness. Each subset, being a combination of included or excluded individual integers, inherently maintains this uniqueness.

Solutions

  • C++
  • Java
  • Python
cpp
class Solution {
public:
    vector<vector<int>> getSubsets(vector<int>& nums) {
        int numsCount = nums.size();
        vector<vector<int>> result;
        for (int i = pow(2, numsCount); i < pow(2, numsCount + 1); ++i) {
            // convert integer to binary string mask
            string binaryMask = bitset<32>(i).to_string().substr(32 - numsCount);
            // pick elements based on binary mask
            vector<int> subset;
            for (int j = 0; j < numsCount; ++j) {
                if (binaryMask.at(j) == '1') subset.push_back(nums[j]);
            }
            result.push_back(subset);
        }
        return result;
    }
};

This C++ solution generates all possible subsets of a given array of integers. The main function getSubsets operates by using binary masking to create each possible combination of the input array elements.

  • The input is a vector of integers, nums.
  • The output is a vector of vectors, where each inner vector is a subset of nums.

The function works as follows:

  1. Calculate the number of elements, numsCount, in the input vector.
  2. Initialize an empty vector of vectors result to store the subsets.
  3. Iterate from 2^numsCount to 2^(numsCount + 1) - 1. Each number in this range represents a binary mask of the elements that will be included in a subset.
  4. For each number:
    • Convert the number to a binary string (binaryMask) that is precisely numsCount characters long, corresponding to each element in the input vector.
    • Initialize an empty vector subset.
    • Iterate through each character in binaryMask. If a character is '1', the corresponding element from nums is added to subset.
    • Add subset to result.
  5. Return the result vector which now contains all subsets.

The binary mask approach efficiently covers all possible combinations of elements because each bit in the mask corresponds to the presence (1) or absence (0) of an element from nums in the subset. Each subset corresponds uniquely to a binary number in the range from 2^numsCount to 2^(numsCount + 1) - 1.

java
class Solution {
    
    public List<List<Integer>> generateSubsets(int[] elements) {
        List<List<Integer>> result = new ArrayList();
        int length = elements.length;
    
        for (int i = (int) Math.pow(2, length); i < (int) Math.pow(2, length + 1); ++i) {
            // convert to binary and skip the highest bit
            String binary = Integer.toBinaryString(i).substring(1);
    
            // create a new subset based on the binary representation
            List<Integer> subset = new ArrayList();
            for (int j = 0; j < length; ++j) {
                if (binary.charAt(j) == '1') subset.add(elements[j]);
            }
            result.add(subset);
        }
        return result;
    }
}

This Java solution effectively generates all possible subsets of an input array of integers. The method generateSubsets initializes by creating an empty list of lists result, which will store each subset. It leverages binary strings to represent the inclusion (1) or exclusion (0) of each element in a subset for the array of length length.

  • Begin by iterating over a range determined by powers of 2, specifically from 2^length to 2^(length+1). This range covers all possible combinations for array elements.
  • For each number in this range, convert it to a binary string and ignore the most significant bit (leftmost bit). This binary representation helps in determining which elements to include in the subset.
  • Iterate through the binary string. If a character is '1', add the corresponding element from the original array to the current subset.
  • Add each constructed subset to result.

Finally, the method returns result, which contains all subsets, including the empty subset, each represented as a list of integers. This implementation provides a clear and straightforward approach to solve the subset generation problem using bitwise operations and binary representations.

python
class Solution:
    def generate_subsets(self, elements: List[int]) -> List[List[int]]:
        total_elements = len(elements)
        results = []
    
        for i in range(2**total_elements, 2 ** (total_elements + 1)):
            bitmask = bin(i)[3:]
            results.append([elements[idx] for idx in range(total_elements) if bitmask[idx] == '1'])
    
        return results

The provided Python code efficiently solves the problem of generating all possible subsets of a given list of integers. It utilizes bitwise operations to generate subsets. Here's how it works:

  • The given list, elements, has its subsets computed based on the length of the list. The generate_subsets method determines the total number of elements in the list (total_elements).
  • The code iterates over a range from 2**total_elements to 2**(total_elements + 1). This range leverages binary counting where each number in the range represents a potential subset.
  • For each number in the range, a binary representation (bitmask) is created by stripping the first three characters of the binary string to align with the indices of the list.
  • A list comprehension is used inside the loop. It checks each character in the bitmask. If a character is '1', the corresponding index in the elements list is chosen. This way, each subset is formed based on the 1's in the bitmask.
  • The subsets are collected in the list results, which is returned at the end of the function.

This approach ensures that all possible combinations of elements are considered without the need for recursive calls, which can lead to a more efficient solution in terms of run time and memory usage, especially for larger lists.

Comments

No comments yet.