Subsets medium

Problem Statement

Given an integer array nums, 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]]

Steps

The problem of finding all subsets is equivalent to generating all binary numbers from 0 to 2ⁿ - 1, where n is the length of the input array. Each bit in the binary number represents whether the corresponding element in the input array is included in the subset or not.

1. Iterate through all possible subsets: We use a loop that iterates from 0 to 2ⁿ - 1.
2. Generate subsets: For each number in the loop, we convert it to its binary representation. Each bit in the binary representation corresponds to an element in the input array. If the bit is 1, we include the element in the current subset; otherwise, we don't.
3. Store subsets: We store the generated subsets in a list of lists.

Explanation

The core idea is to use bit manipulation to efficiently generate all possible combinations. Each integer from 0 to 2ⁿ - 1 represents a unique subset. The binary representation of the integer acts as a mask: a '1' at the i-th bit indicates that the i-th element of the input array is included in the subset.

For example, if nums = [1, 2, 3], then:

• 0 (000) represents the empty subset []
• 1 (001) represents the subset [3]
• 2 (010) represents the subset [2]
• 3 (011) represents the subset [2, 3]
• 4 (100) represents the subset [1]
• 5 (101) represents the subset [1, 3]
• 6 (110) represents the subset [1, 2]
• 7 (111) represents the subset [1, 2, 3]

Code

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public IList<IList<int>> Subsets(int[] nums) {
        IList<IList<int>> result = new List<IList<int>>();
        int n = nums.Length;
        int numSubsets = 1 << n; // 2^n

        for (int i = 0; i < numSubsets; i++) {
            List<int> subset = new List<int>();
            for (int j = 0; j < n; j++) {
                if ((i >> j) % 2 == 1) { // Check if j-th bit is set
                    subset.Add(nums[j]);
                }
            }
            result.Add(subset);
        }

        return result;
    }
}

Complexity

• Time Complexity: O(N * 2^N), where N is the length of the input array. We iterate through 2^N subsets, and for each subset, we potentially add N elements.
• Space Complexity: O(N * 2^N), to store the result. The number of subsets is 2^N, and each subset can contain up to N elements.