algoadvance

Leetcode 78. Subsets

Problem Statement

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:

Input: nums = [1,2,3]
Output: [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

Clarifying Questions

  1. Q: Can the input array contain duplicate elements? A: No, the problem states that the elements are unique.

  2. Q: What is the maximum length of the input array? A: The problem does not specify, but typically LeetCode limits handle up to 20 elements reasonably.

  3. Q: Can the subsets be returned in any order? A: Yes, the order of the subsets in the output does not matter.

Strategy

We can solve this problem using a backtracking approach or using an iterative method. Here, we’ll use the iterative approach:

  1. Start with an empty subset, which is the first subset.
  2. For each element in the input array, iterate over all existing subsets and add the current element to them to create new subsets.
  3. Append these new subsets to the list of all subsets.

This algorithm ensures that all possible combinations of elements are considered to create the complete power set.

Code

#include <vector>

class Solution {
public:
    std::vector<std::vector<int>> subsets(std::vector<int>& nums) {
        std::vector<std::vector<int>> subsets = \{\{}};
        
        for (int num : nums) {
            int n = subsets.size();
            for (int i = 0; i < n; ++i) {
                std::vector<int> newSubset = subsets[i];
                newSubset.push_back(num);
                subsets.push_back(newSubset);
            }
        }
        
        return subsets;
    }
};

Time Complexity

The time complexity of this solution is O(N * 2^N), where N is the number of elements in the input array nums. This is because each element can either be included or excluded in each subset (resulting in 2^N subsets), and we need to create a new subset for each existing subset when processing each new element. Each subset creation operation takes time proportional to the current number of subsets, leading to the N * 2^N complexity.

The space complexity is also O(N * 2^N) due to the storage required for all subsets.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI