Subsets (Take or Skip)

Medium

Every element is either in or out. That binary choice at each index builds a decision tree with 2 to the n leaves.

binary decisionsrecursion tree

TimeO(n * 2^n)

SpaceO(n) recursion depth

InputUp to 4 values

[ ]

modebrute force

in progressbase casereturnedcache hit

At index 0, value 1. Two branches: take it or skip it.

1 / 30

dfs(i, path):

if i == n: record(path); return

path.push(a[i]); dfs(i+1, path); path.pop() // take

dfs(i+1, path) // skip

Why it matters

Always copy the current path when recording it, or later mutations corrupt earlier answers.

Practise this

Keyboard

space play← → stepr restartctrl K search

More in Recursion & Backtracking