Backtrack
Key Points
Thinking Patterns
An Example
Problems
Problems - Permutation, Combination and Set Problems
Generally, there are 3 types of classic problems for Permutation, Combination and Set problems. There maybe some other variants from these 3 types.
1. Choose from a list which contains `Non-Duplicate` elements, and element can ONLY be used for ONE time.
2. Choose from a list which contains `Duplicate` elements, and element can ONLY be used for ONE times.
3. Choose from a list which contains `Non-Duplicate` elements, and element can be used for MULTIPLE times.
Thinking Patterns
And the key points of these problems is the backtrack tree
Problems
| Types | Problems | Key Points | Possible Solutions | Comments |
|---|---|---|---|---|
| Permutation Problems | 46 | code | type 1 | |
| Permutation Problems | 47 | code | type 2 | |
| Combination Problems | 77 | code | type 1 | |
| Combination Problems | 216 | code | type 1 | |
| Combination Problems | 40 | code | type 2 | |
| Combination Problems | 39 | code | type 3 | |
| Set Problems | 78 | code | type 1 | |
| Set Problems | 90 | code | type 2 | |
| Queen Problems | ||||
| Sudo Problems | ||||
| Parentheses Problems |
Problems - Variants Problems
| Types | Problems | Key Points | Possible Solutions | Comments |
|---|---|---|---|---|
| Debt Problem | 465 | code |
References
- https://labuladong.online/algo/essential-technique/backtrack-framework/
- https://labuladong.online/algo/essential-technique/permutation-combination-subset-all-in-one/
- https://labuladong.online/algo/practice-in-action/two-views-of-backtrack/
Problems - Others
Problems
| Problems | Possible Solutions | Key Points | Code | Comments |
|---|---|---|---|---|
| 494. Target Sum | 1. Backtrack 2. DP |
1. Pruning with memo | code |
References