| Problem Names | Solution Writeups | Code |
|---|---|---|
| Subsets |
For each element, choose between add or don't add to. When insert the correct permutation into the list, make sure to copy the permutation list. |
|
| Subsets II |
First sort the array, and then choose between add or don't add. When don't add, before recursively call the backtracking function, update idx to position of next unique elements (Don't do recursion on duplicates). |
|
| Permutations |
Keep popping the first element in the array until size is 1, and then add back removed elements back. |
|
| Combination Sum |
For each numbers can choose between add or don't add. Stop recursion when the sum > target or index out of bound. Add idx by 1 if don't add, else don't change idx since reuse of the same number is allowed. |
|
| Combination Sum II |
Since reuse is not allowed, increase idx in every recursion. Also, sort the array in the start to prevent duplicates. Jump to the next element that is not same as previous when duplicates found. Idea much similar as combination sum. |
|
| Word Search |
Brute force approach only applicable to Python. For each character in the board, search through four possible direction, don't search repeated position. |
|
| Palindrome Partitioning |
Brute force find all possible partitions. Verify if current substring is a palindrome then continue do recursion, else stop. |
|
| Letter Combinations of a Phone Number |
Create map that maps digit to string availables. Then do DFS to generate all possible string combinations. |
|
| N-Queen |
The trick here is that we try putting queen in each row (increasing order), then in each row we try putting queen in each col only if it is valid. To determine if it is valid, we check if the current position (row, col) is column-safe, and is also diagonally safe. To check diagonally safe, we can check if every positive and negative diagonals in all rows above current row does not contain a queen piece. We do not need to check if current pos is row-safe since we used different row everytime we do the DFS. We also dun need to check rows below current row is because we guarantee there is no queen below current row. |