# Tag: Backtracking

Word Break II. If you purely use back tracking, you will run out of time. The trick is to cache the results so that we don’t have to try break…

Palindrome Partitioning. This is a typical backtracking problem.

Sum Root to Leaf Numbers. Just traverse the tree using DFS, when ever you see a full path (a node that has no child tree node), Add the number of…

Restore IP Addresses. A valid of IP segment can be one, two or three digits, just traverse all the possibility by using DFS.

Gray Code. The trick is to use backtracking, basic you want to traverse all the possible combinations with the current bit not changed first, then you traverse all the possible…

Subsets. I solve this problem by using the same method as I used in Combinations. Just find the combinations with all different length.

Combinations. Just use a stack and keep adding number into it. Exhaust all possible combinations and check if the number of numbers in the stack has reached k.

Combination Sum II. Still a DFS on each number in C from smaller to larger, but this time there is limited number of times can be used in each number.