
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:
Understand that a power set of a set with
n
elements contains2^n
subsets, including the empty set and the set itself.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.
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]
.
- Start with an empty subset:
- For example, consider
Each step essentially builds upon the previous subsets forming a tree-like structure where at each node you decide "include" or "not include".
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
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:
- Calculate the number of elements,
numsCount
, in the input vector. - Initialize an empty vector of vectors
result
to store the subsets. - Iterate from
2^numsCount
to2^(numsCount + 1)
- 1. Each number in this range represents a binary mask of the elements that will be included in a subset. - For each number:
- Convert the number to a binary string (
binaryMask
) that is preciselynumsCount
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 fromnums
is added tosubset
. - Add
subset
toresult
.
- Convert the number to a binary string (
- 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
.
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
to2^(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.
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. Thegenerate_subsets
method determines the total number of elements in the list (total_elements
). - The code iterates over a range from
2**total_elements
to2**(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 theelements
list is chosen. This way, each subset is formed based on the1'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.
No comments yet.