Backtracking
Use for permutations, combinations, subsets, N-queens, phone digits.
What this pattern is
Explore the solution space by building partial solutions and undoing decisions (backtrack). Prune impossibilities early. Used for subsets, permutations, combinations, and constraint puzzles.
Exercise: combinationSum
Task: Given distinct candidates and target T, return all unique combinations where numbers sum to T. Unlimited use per candidate.
Example: cands=[2,3,6,7], T=7 → [[7],[2,2,3]]
Edge cases: no solution, large T, many small numbers.
Your Solution
Exercise: permute
Task: Return all permutations of an array of distinct numbers.
Example: [1,2,3] → [[1,2,3],[1,3,2],[2,1,3],...]
Edge cases: duplicates (if allowed, avoid duplicates), empty array.
Your Solution
Exercise: subsets
Task: Generate all subsets (the power set) of an array of unique integers.
Example: [1,2,3] → [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
Edge cases: empty input, duplicates (clarify requirement).