⚠️ This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#78) before relying on it.

Subsets

An interactive visualization of the backtracking algorithm to generate all possible subsets. Watch the decision tree grow as we explore include/exclude choices for each element.

Backtracking LeetCode 78 ↗ Medium

The Problem

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.

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

Interactive Visualization

Array (comma-separated)

Preset

Speed:

Decision Tree

Active Path

Completed

Not Yet Explored

Current Subset

[]

Collected Subsets (0)

Code

fun subsets(nums: IntArray): List<List<Int>> {    val result = mutableListOf<List<Int>>()    fun backtrack(start: Int, current: MutableList<Int>) {        result.add(current.toList())        for (i in start until nums.size) {            current.add(nums[i])  // include            backtrack(i + 1, current)            current.removeAt(current.size - 1)  // backtrack        }    }    backtrack(0, mutableListOf())    return result}

def subsets(nums):    result = []    def backtrack(start, current):        result.append(current[:])        for i in range(start, len(nums)):            current.append(nums[i])  # include            backtrack(i + 1, current)            current.pop()  # backtrack    backtrack(0, [])    return result

Status

Press Step or Play to begin.

How It Works

Key Insight

The backtracking approach explores all possible combinations by making a sequence of choices. For each element, we have two options: include it or skip it. The decision tree visualizes this: each level represents a decision for one element, and each path from root to leaf represents one subset.

The Algorithm

Initialize: Start with an empty result list and an empty current subset
Add current subset: Before exploring further, add a copy of the current subset to results (this includes the empty set at the start)
For each remaining element: Starting from index start to the end of the array:
- Include: Add nums[i] to the current subset
- Recurse: Call backtrack(i + 1, current) to explore all subsets that include this element
- Backtrack: Remove the last element (pop) to explore other branches
The recursion: Each recursive call explores a different decision path, building the complete decision tree
Result: The result list contains all 2ⁿ possible subsets

Why It Works

The algorithm systematically explores every possible subset by treating subset generation as a series of binary decisions (include or exclude). The start parameter ensures we don't revisit earlier elements, avoiding duplicates. By adding the current subset before the loop, we capture every state of the subset as we build it, including the empty set and all partial subsets.

Complexity

Time O(n × 2ⁿ)

Space O(n)

There are 2ⁿ possible subsets for an array of size n. Each subset takes O(n) time to copy into the result. The recursion depth is at most n, requiring O(n) stack space.