Backtracking

Backtracking builds candidates incrementally and abandons a path the moment it can't lead to a valid solution. It's the systematic way to enumerate permutations, combinations, and subsets, and to solve constraint puzzles like N-Queens or Sudoku.

20 LeetCode problems solved with the Backtracking pattern. Practice them with spaced repetition so the pattern sticks.

• Combination SumMEDIUM · O(N^(T/M))
• Combination Sum IIMEDIUM · O(2^n)
• Combination Sum IIIMEDIUM · O(C(9,k) * k)
• CombinationsMEDIUM · O(k * C(n, k))
• Generate ParenthesesMEDIUM · O(4^n / sqrt(n))
• Letter Combinations of a Phone NumberMEDIUM · O(4^n * n)
• Matchsticks to SquareMEDIUM · O(4^n)
• N-QueensHARD · O(n!)
• N-Queens IIHARD · O(n!)
• Non-decreasing SubsequencesMEDIUM · O(2^n * n)
• Palindrome PartitioningMEDIUM · O(n * 2^n)
• Partition to K Equal Sum SubsetsMEDIUM · O(k * 2^n)
• PermutationsMEDIUM · O(n * n!)
• Permutations IIMEDIUM · O(n * n!)
• Restore IP AddressesMEDIUM · O(1)
• SubsetsMEDIUM · O(n * 2^n)
• Subsets IIMEDIUM · O(n * 2^n)
• Sudoku SolverHARD · O(9^m)
• Word Break IIHARD · O(n * 2^n)
• Word SearchMEDIUM · O(m*n*4^L)