Subsets
Problem Description
Given an integer array nums of unique elements, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
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
numsare unique.
Solve it on LeetCode
Approaches
1. Backtracking Approach
The backtracking technique is one of the simplest and intuitive ways to solve this problem. The main idea is to generate all possible subsets incrementally. Here's the detailed procedure:
- Recursion is used to explore inclusion or exclusion of each element in the subset being formed.
- Maintain a current subset list (path) and we include/exclude elements from nums.
- On reaching a point where no more elements are left to consider, record the current subset as a valid solution.
- Start with an empty subset [] and traverse all possible options.
Code:
- Time Complexity: O(2^n) - where
nis the number of elements in nums. Each element can either be included or not included, leading to 2^n possible subsets. - Space Complexity: O(n) - space used by the recursion stack.
2. Iterative Approach
The iterative approach builds the subsets directly using the concepts of combinatorial logic, by iteratively adding each element to existing subsets. Here's the thought process:
- Start with an empty subset.
- For each number in the array, iterate over all subsets formed so far and include the current number into them to form new subsets.
- Merge the newly formed subsets into the result.
Code:
- Time Complexity: O(n * 2^n) - We iterate through n elements, and for each element, we potentially double the number of subsets, resulting in a final complexity of n times 2^n subsets.
- Space Complexity: O(n * 2^n) - Storage for all the subsets.
3. Bit Manipulation Approach
This approach uses the concept that each subset can be represented as a binary string of length n, where 1 indicates inclusion and 0 indicates exclusion.
- There are a total of 2^n subsets possible.
- Each subset corresponds to the binary representation of numbers from 0 to 2^n - 1.
- Convert the numbers into binary form, and include elements in the subset based on digit '1' positioning.
Code:
- Time Complexity: O(n * 2^n) - We generate 2^n subsets, and creating each subset takes O(n) time.
- Space Complexity: O(n * 2^n) - Storage needed for all the subsets.