# Theory

• `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.

# Questions

## Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

``````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.

### Time complexity

4th Catalan number: `(4^n) / (n sqrt(n))`.

`O(n)`

## Given an m x n grid of characters board and a string word, return true if word exists in the grid.

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.

### Time complexity

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)`

## Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

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"

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.

### Time complexity

`O(4^n)`, 7 and 9 has 4 chars.

### Space complexity

`O(n)`, where n = number of digits.