Subsets
Return all possible subsets of the given array.
Pattern fit
This is the gentlest backtracking tree: each element is either taken or skipped. It can also be solved with bitmask enumeration, which makes it a great bridge problem.
Key observation
Each index creates a binary decision, so the whole answer space is a decision tree of depth n.
Target complexity
O(n * 2^n) / O(n)
How to break down the solution cleanly
This is the gentlest backtracking tree: each element is either taken or skipped. It can also be solved with bitmask enumeration, which makes it a great bridge problem.
Each index creates a binary decision, so the whole answer space is a decision tree of depth n.
Model the decision tree explicitly.
Choose the next candidate set for the current depth.
Reference implementation
Python# Generic pattern template
def backtrack(path):
if complete(path):
answer.append(path[:])
return
for choice in choices(path):
if not valid(choice, path):
continue
path.append(choice)
backtrack(path)
path.pop()
Common pitfalls
Forgetting to copy the current path before pushing it into the answer.
Mixing combination indexing and permutation-style used arrays.
Common follow-ups
How would the bitmask version look?
How do duplicates change the recursion?
Continue with related problems
Build repeatable depth inside the Backtracking cluster before moving on.