Twelve problems that drill backtracking from Lesson 15. They all run the same loop — make a choice, recurse, undo the choice — and the differences between subsets, permutations and combinations are tiny (a start index, a used array, a target length). Read the approach, try it, then check the code — every solution here was run and tested.
How to practise. For each problem, write the three lines of the template first: the base case that records a solution, the loop over choices, and the undo. Then add the one twist the problem needs (skip duplicates? prune an invalid choice?). Always record a copy (
path[:]) and never forget the undo. Stuck for 20+ minutes? Read it, close the page, re-solve from memory the next day.
The 12 problems
- 1Subsets (LeetCode 78)MediumReturn every subset of a list of distinct numbers: every node of the backtracking tree is one subset.arrow_forward
- 2Subsets II (LeetCode 90)MediumReturn all unique subsets of a list that may contain duplicates: sort, then skip repeats at the same level.arrow_forward
- 3Permutations (LeetCode 46)MediumReturn every ordering of a list of distinct numbers: fill positions one by one, tracking used elements.arrow_forward
- 4Permutations II (LeetCode 47)MediumReturn all unique orderings of a list with duplicates: sort, and use equal values in left-to-right order.arrow_forward
- 5Combinations (LeetCode 77)MediumReturn every way to choose k numbers from 1..n: a start index keeps picks increasing, stop at length k.arrow_forward
- 6Combination Sum (LeetCode 39)MediumFind all combinations of candidates (reusable) that sum to a target: recurse with i, break when too big.arrow_forward
- 7Combination Sum II (LeetCode 40)MediumFind unique combinations summing to a target, each number used once: sort, skip same-level repeats, break.arrow_forward
- 8Generate Parentheses (LeetCode 22)MediumList every balanced string of n bracket pairs: add '(' while open < n and ')' only while close < open.arrow_forward
- 9Letter Combinations of a Phone Number (LeetCode 17)MediumEvery word a digit string can spell on a phone keypad: one recursion level per digit, one branch per letter.arrow_forward
- 10Palindrome Partitioning (LeetCode 131)MediumSplit a string into palindromic pieces every possible way: try each palindromic prefix, recurse on the rest.arrow_forward
- 11Word Search (LeetCode 79)MediumCan a word be traced through adjacent grid cells without reuse? DFS letter by letter, mark and unmark cells.arrow_forward
- 12N-Queens (LeetCode 51 / 52)HardPlace n queens so none attack each other: one queen per row, prune columns and diagonals with three sets.arrow_forward