GenerateParens is a good starter question on backtracking.Primarly there are 3 main parts: 1. Like an recursion question, identify the terminating condition(s). Don't forget to add out of bound index checks as part of your terminating conditions. 2. Recurse to form a combination (or do something else). 3. Backtrack on the result of #2, so other combinations can be formed.
Example 1:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Example 2:
Input: n = 1
Output: ["()"]
Implementation: GenerateParens
We add a ( only if there are some to add, aka, the number of open brackets is less than n. We only add a closing bracket if there are enough open brackets to add them for, so the number of open and closed brackets are balanced.
4th Catalan number: (4^n) / (n sqrt(n)).
O(n)
The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
Example 1:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
Example 2:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true
Example 3:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false
Implementation: WordSearch
Since we don't know where the word is going to start from, we need to start from every char in the matrix. Once we start from a char, we keep travelling along the path where the char matches with the chars in the word. If we reach the end on any path, we got the word.
Another thing we need to take care of is track the cells we have traversed, so we don't end up using a cell twice in a path.
We are traversing from every cell, so for a 2-D matrix, that's O(n^2). From every cell, we have the option of choosing 4 paths, so that's O(4^n). So complexity is O(4^n).
O(n^2)
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example 1:
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:
Input: digits = ""
Output: []
Example 3:
Input: digits = "2"
Output: ["a","b","c"]
Implementation: PhoneNumberLetterCombinations
The number of letters in a combination made would be the number of digits in the input, because each digit, at most, can correspond to one char in the output. So our terminating condition is only when the number of chars equals the number of digits.
So we need to combine the elements like so:
which is fixing the chars of a digit, trying out a combination, backtracking, and trying out a different combination.
O(4^n), 7 and 9 has 4 chars.
O(n), where n = number of digits.