MediumBlind75ArrayBacktracking

Subsets

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

Examples

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

All possible subsets.

Input
nums = [0]
Output
[[],[0]]

The power set of [0] is [[],[0]].

Constraints

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

Approaches

Use bitmask to generate all subsets.

CodeT: O(n * 2^n) | S: O(n * 2^n)
def subsets(nums):
    result = []
    n = len(nums)
    for mask in range(1 << n):
        subset = []
        for i in range(n):
            if mask & (1 << i):
                subset.append(nums[i])
        result.append(subset)
    return result

Use backtracking to generate subsets by including or excluding each element.

CodeT: O(n * 2^n) | S: O(n)
def subsets(nums):
    result = []
    def backtrack(start, current):
        result.append(current[:])
        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()
    backtrack(0, [])
    return result

Start with empty set and add each number to all existing subsets.

Diagram

nums = [1,2,3] Start: [[]] Add 1: [[],[1]] Add 2: [[],[1],[2],[1,2]] Add 3: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
CodeT: O(n * 2^n) | S: O(n * 2^n)
def subsets(nums):
    result = [[]]
    for num in nums:
        result += [curr + [num] for curr in result]
    return result

Complexity Comparison

Iterative - Bit Manipulation
T: O(n * 2^n)S: O(n * 2^n)

Use bitmask to generate all subsets.

Backtracking
T: O(n * 2^n)S: O(n)

Use backtracking to generate subsets by including or excluding each element.

Cascading
T: O(n * 2^n)S: O(n * 2^n)

Start with empty set and add each number to all existing subsets.

Common Mistakes

Not handling duplicate elements (though this problem guarantees uniqueness)

Using the wrong index in backtracking (should be i+1 not start+1)

Forgetting to add the empty subset

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems