# LeetCode All Problems Solution Index: Backtracking, Greedy and DP

## Overview

I have summarized the solutions to LeetCode problems by organizing them into closely related categories (backtracking, greedy and DP) and give tree index page for quick references.

## LeetCode All Problems Solution Index: Backtracking, Greedy and DP

- Game Problems: Solve a game, DFS + Prune, validate a solution, e.g., N-queens, Combination sum, Permutations, Sudoku, 24 points and so on.
- N-Queens II 2012-03-20 32.5% (Hard) Solution
- N-Queens 2012-03-19 25.7% (Hard) Solution
- Sudoku Solver 2012-03-04 20.8% (Hard) Solution

- Backtracking (DFS): Be careful about duplicates, and maybe you need to do push_back() before recursively call dfs(), and then do not forget pop_back() afterwards. Pruning could be adopted to make it more efficiently.
- Scramble String 2012-04-30 22.4% (Hard)
- Gray Code 2012-05-20 31.9% (Medium) Solution
- Letter Combinations of a Phone Number 2012-01-26 26.0% (Medium) Solution
- Combinations 2012-04-18 30.0% (Medium) Solution
- Combination Sum II 2012-03-06 24.2% (Medium) Solution
- Combination Sum 2012-03-06 26.3% (Medium) Solution
- Permutations II 2012-03-16 24.6% (Hard) Solution
- Permutations 2012-03-16 31.0% (Medium) Solution
- Permutation Sequence 2012-03-27 21.8% (Medium) Solution
- Next Permutation 2012-02-25 25.2% (Medium) Solution PS: actually not related to DFS/Backtracking, but it is also about permutation so I put it here
- Subsets II 2012-06-25 26.6% (Medium) Solution
- Subsets 2012-04-18 27.5% (Medium) Solution

- Greedy: Need clever mind and find the optimal sub-structure
- Jump Game 2012-03-24 27.1% (Medium) Solution
- Jump Game II 2012-03-16 24.2% (Hard) Solution

- Dynamic Programming: The Recursive DP function is the key! Memory Optimization is also interesting when current state only depends on previous step (e.g., n - 1) rather than all the previous states
- Rectangle/Histogram problems (e.g., area, skyline) on 2-Dimentional plane, the following 4 relates with each other: Largest Rectangle solution could solve 1) itself; 2) Maximual Rectagle; 3) Trapping Rain Water; while Container with most Water has the left/right bound similar to Largest rectangle problem but do not care about those lines in between the left and right bounds
- Largest Rectangle in Histogram 2012-04-22 20.9% (Hard) Solution
- Maximal Rectangle 2012-04-23 21.6% (Hard) Solution
- Trapping Rain Water 2012-03-10 28.4% (Hard) Solution
- Container With Most Water 2012-01-08 30.6% (Medium) Solution

- Contiguous Subarray: A common trick could be applied to come up with the DP formula:
- Maximum Subarray 2012-03-21 34.0% (Medium) Solution
- Maximum Product Subarray 2014-09-23 16.2% (Medium) Solution

- Best Time to Buy and Sell Stocks Series: extended problem to allow at most k transactions is hard, any easy to understand references for this k transaction problem?
- Best Time to Buy and Sell Stock III 2012-11-06 22.0% (Hard) Solution
- Best Time to Buy and Sell Stock II 2012-10-30 36.6% (Medium) Solution This is actually a greedy problem, I put it here for comparison purpose for the buy and sell stock problems
- Best Time to Buy and Sell Stock 2012-10-30 31.0% (Medium) Solution

- String DP Problems: Usually derive the recursive formula by consider whether or not include the last character in the string, the very essential classic one should actually be the "longest common subsequence" problem (LCS)
- Edit Distance 2012-04-04 25.0% (Hard) Solution
- Longest Valid Parentheses 2012-02-29 19.1% (Hard) Solution
- Longest Palindromic Substring 2011-11-11 20.4% (Medium) Solution
- Palindrome Partitioning II 2013-02-28 17.8% (Hard) Solution
- Palindrome Partitioning 2013-02-27 25.7% (Medium) Solution

- Other DP:
- Decode Ways 2012-06-25 15.8% (Medium) Solution
- Minimum Path Sum 2012-03-28 31.0% (Medium) Solution
- Triangle 2012-10-29 26.5% (Medium) Solution
- Climbing Stairs 2012-04-03 33.4% (Easy) Solution
- Unique Paths II 2012-03-28 27.6% (Medium) Solution
- Unique Paths 2012-03-28 31.0% (Medium) Solution

- Rectangle/Histogram problems (e.g., area, skyline) on 2-Dimentional plane, the following 4 relates with each other: Largest Rectangle solution could solve 1) itself; 2) Maximual Rectagle; 3) Trapping Rain Water; while Container with most Water has the left/right bound similar to Largest rectangle problem but do not care about those lines in between the left and right bounds

## Summary

I have summarized the solutions to LeetCode problems by organizing them into closely related categories (backtracking, greedy and DP) and give tree index page for quick references. I will keep updating the content as well as this index page as time goes. Please feel free to leave any comments.

Written on March 26, 2015