78. Subsets

This problem asks to find all possible subsets (power set) of a given integer array nums containing unique elements. The solution must not contain duplicate subsets and can be returned in any order.

Approach 1: Depth-First Search (DFS) - Backtracking

This approach uses recursion to explore all possible combinations. The core idea is to iterate through the input array. For each element, we have two choices: either include it in the current subset or exclude it. This decision branching is handled recursively.

Algorithm:

1. Base Case: If we've reached the end of the input array (i == nums.length), we've formed a complete subset. Add a copy of the current subset (t) to the result (ans).

2. Recursive Steps:

   • Exclude: Recursively call the function dfs(i + 1) to explore subsets without the current element.
   • Include: Add the current element (nums[i]) to the current subset (t), then recursively call dfs(i + 1) to explore subsets including the current element. After the recursive call, remove the element (nums[i]) from t (backtracking) to explore other possibilities.

3. Initialization: Start the recursion with dfs(0).

Time Complexity: O(N * 2N). There are 2N possible subsets, and constructing each subset takes O(N) time in the worst case (when the subset contains all elements).

Space Complexity: O(N). The space is primarily used by the recursion stack, which has a depth of at most N.

Code (Python3):

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []
        t = []
 
        def dfs(i: int):
            if i == len(nums):
                ans.append(t.copy())  #Important: Append a copy, not t itself.
                return
            dfs(i + 1)  # Exclude
            t.append(nums[i])
            dfs(i + 1)  # Include
            t.pop()
 
        dfs(0)
        return ans

Code (Java):

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> t = new ArrayList<>();
 
    public List<List<Integer>> subsets(int[] nums) {
        dfs(nums, 0);
        return ans;
    }
 
    private void dfs(int[] nums, int i) {
        if (i == nums.length) {
            ans.add(new ArrayList<>(t)); //Important: Create a copy.
            return;
        }
        dfs(nums, i + 1); // Exclude
        t.add(nums[i]);
        dfs(nums, i + 1); // Include
        t.remove(t.size() - 1);
    }
}

Similar implementations can be written in other languages (C++, Go, Javascript, etc.) following the same logic.

Approach 2: Binary Enumeration

This approach leverages the fact that each subset can be represented by a unique binary number of length N (where N is the number of elements in nums). Each bit in the binary number corresponds to an element in nums. A bit set to 1 indicates the element is included in the subset, and 0 indicates exclusion.

Algorithm:

1. Iterate through all possible binary numbers from 0 to 2N - 1.

2. For each binary number (mask):

   • Create an empty subset (t).
   • Iterate through the bits of mask. If the ith bit is 1, add nums[i] to t.
   • Add t to the result (ans).

Time Complexity: O(N * 2N). Similar to DFS, we iterate through all subsets (2N), and building each subset takes O(N).

Space Complexity: O(N). Space is used to store the current subset and the result.

Code (Python3):

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []
        for mask in range(1 << len(nums)):
            subset = []
            for i in range(len(nums)):
                if (mask >> i) & 1:
                    subset.append(nums[i])
            ans.append(subset)
        return ans
 

Similar code can be written for other languages using bit manipulation. The core idea remains the same: iterate through all possible binary numbers and build subsets based on the bit representation.

Both approaches solve the problem efficiently. The choice between them often comes down to personal preference or coding style. The binary enumeration approach might appear slightly more concise in some languages.