Subsets

BacktrackingRecursion

20 min

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.

Example

Example 1:

Input: nums = [1,2,3]

[]

[1]

[2]

[1, 2]

[3]

[1, 3]

[2, 3]

[1, 2, 3]

Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Solution

The core idea of backtracking is to build a solution step-by-step and abandon a path as soon as it is determined that it cannot lead to a valid solution. For the subsets problem, we can think of it as a decision tree where at each level, we decide whether to include the current number in our subset or not.

Algorithm Steps

Define a recursive function, let's call it `backtrack`, that takes the current index and the current subset as arguments.
First, add the current subset to our list of all subsets.
Iterate from the current index to the end of the `nums` array.
In each iteration:
- Include the number `nums[i]` in the current subset.
- Recursively call `backtrack` with the next index `i + 1` and the updated subset.
- Backtrack: remove `nums[i]` from the current subset to explore other possibilities.
Start the process by calling `backtrack(0, [])`.

Subsets Visualization

Step-by-step backtracking algorithm

Progress1 / 1

Ready to start the visualization

Input Array

Current Subset

[]

Valid Solutions

No solutions found yet...

Subsets Solution


class Solution:
    def subsets(self, nums: list[int]) -> list[list[int]]:
        res = []
        subset = []

        def dfs(i):
            if i >= len(nums):
                res.append(subset.copy())
                return

            # Decision to include nums[i]
            subset.append(nums[i])
            dfs(i + 1)

            # Decision NOT to include nums[i]
            subset.pop()
            dfs(i + 1)
        
        dfs(0)
        return res