Backtracking — DSA Mastery

Subsets Decision Tree — [1, 2, 3]

At each level, we decide: include this number or skip it. Every path from root to leaf = one subset.

Current path: []

Results found: []

Press Build Tree to animate the backtracking process.

The 3-Step Pattern

CHOOSE — add to path

path.append(choice)

EXPLORE — recurse deeper

backtrack(path, next_choices)

UNCHOOSE — remove from path (the KEY step)

path.pop() — this is what makes it backtracking!

Always copy path when saving result

results.append(path[:]) — NOT results.append(path). List is a reference — if you append path itself, all results will be the same (empty) list at the end.

Subsets vs Permutations vs Combinations

Problem	Key Difference	Complexity
Subsets of [1,2,3]	Use `start` index — only go forward	O(2ⁿ)
Permutations of [1,2,3]	Use `used[]` array — any unused element	O(n!)
Combinations (n choose k)	`start` + stop when path length = k	O(C(n,k))

Subsets use start to avoid duplicates

By starting the loop at start (not 0), we ensure [1,2] is generated but not [2,1]. Order doesn't matter for subsets.

Pruning — Make It Faster

Pruning = Skip paths that can't lead to valid solutions

If you detect early that a partial path violates the constraints, return immediately. Don't explore children that are guaranteed to fail. This can dramatically reduce the search space.

def backtrack(path, start):
    if violates_constraint(path):
        return  # prune! don't explore further
    if is_complete(path):
        results.append(path[:])
        return
    ...

Subsets + Permutations

# Subsets — use start index
def subsets(nums):
    res, path = [], []
    def bt(start):
        res.append(path[:])         # add at every node
        for i in range(start, len(nums)):
            path.append(nums[i])    # choose
            bt(i + 1)               # explore
            path.pop()              # unchoose
    bt(0); return res

# Permutations — use used[] array
def permute(nums):
    res, path = [], []
    used = [False] * len(nums)
    def bt():
        if len(path) == len(nums):
            res.append(path[:]); return
        for i in range(len(nums)):
            if not used[i]:
                used[i] = True; path.append(nums[i])
                bt()
                used[i] = False; path.pop()
    bt(); return res

LeetCode Problems

MediumSubsetsstart index
MediumPermutationsused[] array
MediumCombinationsstart + stop at k
MediumCombination SumReuse elements, target
MediumWord SearchDFS + in-place visited
HardN-QueensRow by row + attack check
HardSudoku SolverCell by cell + constraint check