DSAverse

Recursion

Loading Recursion Visualizer...

Recursion Tree

depth: 1

f(n) = f(n-1) + f(n-2)

Back to Recursion

Subsets / Power Set

At each element, make a binary choice — include or exclude. Watch the decision tree grow as all 2ⁿ subsets emerge.

Binary Decision Tree

O(n · 2ⁿ) time

8 subsets for n=3

Binary Decision Tree

current on path visited

included excluded deciding

E = exclude I = includeLeaves show resulting subset

Click Play to begin subset generation.

Subsets Found: 0/ 8 total

None found yet...

Recursive Backtracking (Python)

Python

def subsets(nums):
    result = []

    def backtrack(index, current):
        if index == len(nums):
            result.append(current[:])   # record subset
            return
        # Exclude nums[index]
        backtrack(index + 1, current)
        # Include nums[index]
        current.append(nums[index])
        backtrack(index + 1, current)
        current.pop()                   # backtrack

    backtrack(0, [])
    return result

# [1, 2, 3] → 8 subsets

Controls

Array: [1, 2, 3]

Speed: 800ms / step

FastSlow

Progress1 / 0

Current State

Element index0 / 3

Current subset∅

ActionSTART

Depth0

Complexity

TimeO(n · 2ⁿ)

SpaceO(n · 2ⁿ)

Subsets2^3 = 8

Used in: combination sum, letter combos, unique paths, interview problems requiring all combinations.

Test Yourself

Q1/3