Subsets

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

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;
    }
};