Subsets

Given an integer array of unique elements, return all possible subsets (the power set)

Language Selection

Choose your preferred programming language

Showing: Python

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.

Constraints:

1 <= nums.length <= 10
-10 <= nums[i] <= 10
All the numbers of nums are unique

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]]

Example 3:

Input: nums = [1,2]
Output: [[],[1],[2],[1,2]]
Explanation: The power set includes the empty set and all combinations of elements.

Approach 1: Iterative (Build on Previous Subsets)

Algorithm:

Start with an empty subset [[]]
For each number in the array, take all existing subsets and create new subsets by adding the current number to each
Append the new subsets to the result

Time Complexity: O(n * 2^n) Space Complexity: O(n * 2^n)

Python:

def subsets(nums):
    """
    Generate all subsets iteratively by building on previous subsets
    Time: O(n * 2^n)
    Space: O(n * 2^n)
    """
    result = [[]]

    for num in nums:
        # For each existing subset, create a new subset with num appended
        result += [subset + [num] for subset in result]

    return result

Java:

class Solution {
    /**
     * Generate all subsets iteratively by building on previous subsets
     * Time: O(n * 2^n)
     * Space: O(n * 2^n)
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());

        for (int num : nums) {
            int size = result.size();
            for (int i = 0; i < size; i++) {
                List<Integer> newSubset = new ArrayList<>(result.get(i));
                newSubset.add(num);
                result.add(newSubset);
            }
        }

        return result;
    }
}

Go:

// subsets - Generate all subsets iteratively by building on previous subsets
// Time: O(n * 2^n)
// Space: O(n * 2^n)
func subsets(nums []int) [][]int {
    result := [][]int{{}}

    for _, num := range nums {
        size := len(result)
        for i := 0; i < size; i++ {
            newSubset := make([]int, len(result[i]))
            copy(newSubset, result[i])
            newSubset = append(newSubset, num)
            result = append(result, newSubset)
        }
    }

    return result
}

JavaScript:

/**
 * Generate all subsets iteratively by building on previous subsets
 * Time: O(n * 2^n)
 * Space: O(n * 2^n)
 */
function subsets(nums) {
    let result = [[]];

    for (const num of nums) {
        const size = result.length;
        for (let i = 0; i < size; i++) {
            result.push([...result[i], num]);
        }
    }

    return result;
}

C#:

public class Solution {
    /// <summary>
    /// Generate all subsets iteratively by building on previous subsets
    /// Time: O(n * 2^n)
    /// Space: O(n * 2^n)
    /// </summary>
    public IList<IList<int>> Subsets(int[] nums) {
        IList<IList<int>> result = new List<IList<int>>();
        result.Add(new List<int>());

        foreach (int num in nums) {
            int size = result.Count;
            for (int i = 0; i < size; i++) {
                List<int> newSubset = new List<int>(result[i]);
                newSubset.Add(num);
                result.Add(newSubset);
            }
        }

        return result;
    }
}

Approach 2: Backtracking

Algorithm:

Use a recursive function that builds subsets by choosing to include or exclude each element
At each index, add the current subset to the result
Iterate from the current index forward, adding each element and recursing
Backtrack by removing the last element after recursion

Time Complexity: O(n * 2^n) Space Complexity: O(n * 2^n)

Python:

def subsets(nums):
    """
    Generate all subsets using backtracking
    Time: O(n * 2^n)
    Space: O(n * 2^n)
    """
    result = []

    def backtrack(start, current):
        result.append(current[:])  # Add a copy of the current subset

        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()  # Backtrack

    backtrack(0, [])
    return result

Java:

class Solution {
    /**
     * Generate all subsets using backtracking
     * Time: O(n * 2^n)
     * Space: O(n * 2^n)
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] nums, int start, List<Integer> current,
                           List<List<Integer>> result) {
        result.add(new ArrayList<>(current));

        for (int i = start; i < nums.length; i++) {
            current.add(nums[i]);
            backtrack(nums, i + 1, current, result);
            current.remove(current.size() - 1);  // Backtrack
        }
    }
}

Go:

// subsets - Generate all subsets using backtracking
// Time: O(n * 2^n)
// Space: O(n * 2^n)
func subsets(nums []int) [][]int {
    var result [][]int

    var backtrack func(start int, current []int)
    backtrack = func(start int, current []int) {
        // Add a copy of the current subset
        subset := make([]int, len(current))
        copy(subset, current)
        result = append(result, subset)

        for i := start; i < len(nums); i++ {
            current = append(current, nums[i])
            backtrack(i+1, current)
            current = current[:len(current)-1] // Backtrack
        }
    }

    backtrack(0, []int{})
    return result
}

JavaScript:

/**
 * Generate all subsets using backtracking
 * Time: O(n * 2^n)
 * Space: O(n * 2^n)
 */
function subsets(nums) {
    const result = [];

    function backtrack(start, current) {
        result.push([...current]);

        for (let i = start; i < nums.length; i++) {
            current.push(nums[i]);
            backtrack(i + 1, current);
            current.pop();  // Backtrack
        }
    }

    backtrack(0, []);
    return result;
}

C#:

public class Solution {
    /// <summary>
    /// Generate all subsets using backtracking
    /// Time: O(n * 2^n)
    /// Space: O(n * 2^n)
    /// </summary>
    public IList<IList<int>> Subsets(int[] nums) {
        IList<IList<int>> result = new List<IList<int>>();
        Backtrack(nums, 0, new List<int>(), result);
        return result;
    }

    private void Backtrack(int[] nums, int start, List<int> current,
                           IList<IList<int>> result) {
        result.Add(new List<int>(current));

        for (int i = start; i < nums.Length; i++) {
            current.Add(nums[i]);
            Backtrack(nums, i + 1, current, result);
            current.RemoveAt(current.Count - 1);  // Backtrack
        }
    }
}

Approach 3: Bit Manipulation

Algorithm:

For an array of n elements, there are 2^n subsets
Each subset can be represented by a bitmask of n bits
If bit j is set in mask i, include nums[j] in subset i
Iterate through all masks from 0 to 2^n - 1

Time Complexity: O(n * 2^n) Space Complexity: O(n * 2^n)

Python:

def subsets(nums):
    """
    Generate all subsets using bit manipulation
    Time: O(n * 2^n)
    Space: O(n * 2^n)
    """
    n = len(nums)
    result = []

    for mask in range(1 << n):  # 0 to 2^n - 1
        subset = []
        for j in range(n):
            if mask & (1 << j):
                subset.append(nums[j])
        result.append(subset)

    return result

Java:

class Solution {
    /**
     * Generate all subsets using bit manipulation
     * Time: O(n * 2^n)
     * Space: O(n * 2^n)
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;

        for (int mask = 0; mask < (1 << n); mask++) {
            List<Integer> subset = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if ((mask & (1 << j)) != 0) {
                    subset.add(nums[j]);
                }
            }
            result.add(subset);
        }

        return result;
    }
}

Go:

// subsets - Generate all subsets using bit manipulation
// Time: O(n * 2^n)
// Space: O(n * 2^n)
func subsets(nums []int) [][]int {
    n := len(nums)
    var result [][]int

    for mask := 0; mask < (1 << n); mask++ {
        var subset []int
        for j := 0; j < n; j++ {
            if mask&(1<<j) != 0 {
                subset = append(subset, nums[j])
            }
        }
        result = append(result, subset)
    }

    return result
}

JavaScript:

/**
 * Generate all subsets using bit manipulation
 * Time: O(n * 2^n)
 * Space: O(n * 2^n)
 */
function subsets(nums) {
    const n = nums.length;
    const result = [];

    for (let mask = 0; mask < (1 << n); mask++) {
        const subset = [];
        for (let j = 0; j < n; j++) {
            if (mask & (1 << j)) {
                subset.push(nums[j]);
            }
        }
        result.push(subset);
    }

    return result;
}

C#:

public class Solution {
    /// <summary>
    /// Generate all subsets using bit manipulation
    /// Time: O(n * 2^n)
    /// Space: O(n * 2^n)
    /// </summary>
    public IList<IList<int>> Subsets(int[] nums) {
        IList<IList<int>> result = new List<IList<int>>();
        int n = nums.Length;

        for (int mask = 0; mask < (1 << n); mask++) {
            List<int> subset = new List<int>();
            for (int j = 0; j < n; j++) {
                if ((mask & (1 << j)) != 0) {
                    subset.Add(nums[j]);
                }
            }
            result.Add(subset);
        }

        return result;
    }
}

Key Insights

Power Set Size: An array of n elements has exactly 2^n subsets, including the empty set and the full set.
Iterative Build-Up: Each new element doubles the number of subsets by creating copies of all existing subsets with the new element appended.
Backtracking Decision Tree: At each position, we decide whether to include or skip the element. The start index ensures no duplicates and maintains order.
Bitmask Bijection: There is a one-to-one correspondence between n-bit binary numbers and subsets of an n-element set, making bit manipulation a natural approach.
No Duplicates Guaranteed: Since all elements are unique and we process them in order (using start index or bit positions), duplicate subsets are inherently avoided.

Edge Cases

Single element: [1] produces [[], [1]]
Two elements: [1,2] produces [[], [1], [2], [1,2]]
Negative numbers: [-1,0,1] works identically since values do not affect the combinatorial logic
Maximum size: nums.length = 10 produces 1024 subsets, which is manageable

Test Cases

# Test case 1: Standard case
assert sorted(subsets([1,2,3])) == sorted([[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]])

# Test case 2: Single element
assert sorted(subsets([0])) == sorted([[],[0]])

# Test case 3: Two elements
assert sorted(subsets([1,2])) == sorted([[],[1],[2],[1,2]])

# Test case 4: Negative numbers
assert sorted(subsets([-1,0])) == sorted([[],[-1],[0],[-1,0]])

# Test case 5: Larger array
result = subsets([1,2,3,4])
assert len(result) == 16  # 2^4 = 16 subsets

Common Mistakes

Forgetting the empty subset: The power set always includes the empty set [].
Not copying the current list in backtracking: Appending a reference instead of a copy leads to all subsets being the same (empty) list after backtracking completes.
Incorrect start index: Using 0 instead of start in the backtracking loop produces duplicate subsets like [1,2] and [2,1].
Off-by-one in bit manipulation: Using 1 << n as the upper bound (exclusive) is correct; using (1 << n) - 1 misses the full set.
Modifying result subsets after insertion: In languages with mutable lists, modifying a subset after adding it to the result corrupts previously stored subsets.

Language Selection

Subsets

Problem Statement

Approach 1: Iterative (Build on Previous Subsets)

Approach 2: Backtracking

Approach 3: Bit Manipulation

Key Insights

Edge Cases

Test Cases

Common Mistakes

Share this