# Recursion and Dynamic Programming

## Come on, you can do it :)

## Dynamic programming is mostly just a matter of taking a recursive algorithm and finding the overlapping subproblems. You then cache the results for future recursive calls.

## There are generally 2 approaches to such questions

- Memoisation

Looking at the tree above, you see that fib(3) appears twice etc…so we should do caching to save on amount of work done.

- Bottom-Up Approach -> Solve the problem for a simple case, then build up the solution.

This can be thought of as similar to doing the recursive memoized approach but in reverse.

First, we compute fib(1) and fib(0), which are already known from the base cases. Then we use those to compute fib(2). Then we use the prior answers to compute fib(3), then fib(4) and so on.

## How to determine when to give a dynamic programming solution?

- When the problem is recursive and can be built off subproblems.
- “Design an algorithm to compute the nth…” “Write code to list the first nth…” “Implement a method to compute
**all**..” - Find the biggest…

**Extra Questions (Hard -> to do if i am free and want to level up my thinking skills)**

Burst Balloons

https://www.youtube.com/watch?v=uG_MtaCJIrM

# Interview Cake — Practice Question

## Qns 1 a: Write a recursive method for generating all permutations of an input string. Return them as a set.

Definition of permutation: Any ordering of words. For eg, “cat” has the following permutation:

`cat`

cta

atc

act

tac

tca

If we want to form the permutation of **cats**, and we have all the permutations of **cat**,** **then** **what we need to do is to put “**s**” in each possible position in each of these permutations.

Now that we can break the problem into subproblem, we just need a base case and we have a recursive algorithm.

public static List singletonList(T o)

Parameters:This method takes the objectoas a parameter to be stored in the returned list.

Return Value:This method returns animmutable listcontaining only the specified object.

## Qns 1 b: Given a collection of **distinct** integers, return all possible permutations.

**Example:**

**Input:** [1,2,3]

**Output:**

[

[1,2,3],

[1,3,2],

[2,1,3],

[2,3,1],

[3,1,2],

[3,2,1]

]

The trick to understanding the code here is very simple: Simply write out and follow through the code with a simple example, for eg [1,2,3]

- We first traverse to the end of the int array. Return the last element of the num array as a list. For eg, if last element is 3, we return [[3]]
- Then, the caller function will receive this returned list.
- At the caller function, the second last element -> The element before -> will be stored in a variable called firstChar. This firstChar will then be inserted in all possible positions of the returned list. For eg, here, firstChar=2. So after going through line 24–34, the output finalised list will be [[2,3],[3,2]]
- Again, this list will be returned to the previous caller function. Repeating 3, we then get

[[1,2,3],[2,1,3],[2,3,1],

[1,3,2,],[3,1,2],[3,2,1]]

This gives us all the permutations :)

- Might be better to use HashSet instead of List because List can have duplicates.

## Leet Code 47 Permutations II

Given a collection of numbers, `nums`

, that might contain duplicates, return *all possible unique permutations **in any order**.*

**Use HashSet**

## Qns 1c: Leetcode 22. Generate Parentheses

**Brute Force:** To generate all possible permutations like Qns 1a, 1b. Then check the validity of each permutation and discard those invalid ones.

**More efficient solution:** Think of it as trying out every permutation of the string, deciding whether to add an open-bracket or close-bracket to a string.

- The first char of the string must always be a
**(, hence i start by initialising the base string to only contain (.** - If the number of
**(**is smaller than the number of**),**only then we can add**)** - We can always add
**(**as long as there are**(**

For this, we notice that we cannot really return the ArrayList<String> of all possible permutations because we want to have a complete string each time we return something (unlike previous 1a,1b questions where we will create the new permutation based on the returned permutations). So i created a public static ArrayList instead and we will append all possible combinations to this.

## Qns 2: **Write a method fib() that takes an integer n and returns the nth Fibonacci number.**

*A pretty easy dynamic programming question..*

Fib(0) // 0

Fib(1) // 1

Fib(2) //1

Fib(3) //2

Fib(4) //3

## Qns 3: Your quirky boss collects rare, old coins… (Also Leet Code 322)

You are given coins of different denominations and a total amount of money *amount*. Write a function to **compute the fewest number of coins **that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return `-1`

.

You may assume that you have an infinite number of each kind of coin.

## Leet Code 518 (Follow up Qns) Coin Change 2

You are given coins of different denominations and a total amount of money. Write a function to compute the **number of combinations** that make up that amount. You may assume that you have infinite number of each kind of coin.

Return all METHODS.

**Example 1:**

**Input:** amount = 5, coins = [1, 2, 5]

**Output:** 4

**Explanation:** there are four ways to make up the amount:

5=5

5=2+2+1

5=2+1+1+1

5=1+1+1+1+1

**Example 2:**

**Input:** amount = 3, coins = [2]

**Output:** 0

**Explanation:** the amount of 3 cannot be made up just with coins of 2.

**Example 3:**

**Input:** amount = 10, coins = [10]

**Output:** 1

## Leet Code 39. Combination Sum (similar to coin change)

Given an array of **distinct** integers `candidates`

and a target integer `target`

, return *a list of all **unique combinations** of *`candidates`

* where the chosen numbers sum to *`target`

*.* You may return the combinations in **any order**.

The **same** number may be chosen from `candidates`

an **unlimited number of times**. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is **guaranteed** that the number of unique combinations that sum up to `target`

is less than `150`

combinations for the given input.

**Example 1:**

**Input:** candidates = [2,3,6,7], target = 7

**Output:** [[2,2,3],[7]]

**Explanation:**

2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.

7 is a candidate, and 7 = 7.

These are the only two combinations.

**Example 2:**

**Input:** candidates = [2,3,5], target = 8

**Output:** [[2,2,2,2],[2,3,3],[3,5]]

**Example 3:**

**Input:** candidates = [2], target = 1

**Output:** []

**Example 4:**

**Input:** candidates = [1], target = 1

**Output:** [[1]]

**Example 5:**

**Input:** candidates = [1], target = 2

**Output:** [[1,1]]

## Leet Code 40. Combination Sum II

Given a collection of candidate numbers (`candidates`

) and a target number (`target`

), find all unique combinations in `candidates`

where the candidate numbers sum to `target`

.

Each number in `candidates`

may only be used **once** in the combination.

**Note:** The solution set must not contain duplicate combinations.

**Example 1:**

**Input:** candidates = [10,1,2,7,6,1,5], target = 8

**Output:**

[

[1,1,6],

[1,2,5],

[1,7],

[2,6]

]

**Example 2:**

**Input:** candidates = [2,5,2,1,2], target = 5

**Output:**

[

[1,2,2],

[5]

]

Line 52 skips duplicates because consider when we are at recursion R1. For eg, if we have [1,1,2] where the start is at index 0, the first 1, we skip evaluating the second 1 at line 52. This second 1 will then be evaluated in the next recursion R2 where start=1. Here, tempList will then contain [1,1] where 1 comes from the first index 0 and the second 1 comes from the second index 1.

If we did not skip (do not have line 52), then it could be that at R2, the tempList would be [1,1], where both 1s comes from the same second index of the original int[] cand. For example, we add in the first 1 (in index 1, second 1) was added in R1 and the second 1 (index 1) was repeatedly added in R2.

Hence, duplicates.

## Leet Code 279. Perfect Squares

Given a positive integer *n*, find the least number of perfect square numbers (for example, `1, 4, 9, 16, ...`

) which sum to *n*.

**Example 1:**

**Input:** *n* = 12

**Output:** 3

**Explanation: **12 = 4 + 4 + 4.

**Example 2:**

**Input:** *n* = 13

**Output:** 2

**Explanation: **13 = 4 + 9.

This question is similar to Coin Change…

`dp[n] = Min{ dp[n - i*i] + 1 }, n - i*i >=0 && i >= 1`

## Qns 4: **You are a renowned thief who has recently switched from stealing precious metals to stealing cakes because of the insane profit margins. You end up hitting the jackpot, breaking into the world’s largest privately owned stock of cakes — the vault of the Queen of England.**

While Queen Elizabeth has a *limited number of types of cake*, she has an *unlimited supply of each type*.

Each type of cake has a weight and a value, stored in objects of a CakeType class:

Each type of cake has a weight and a value, stored in objects of a CakeType class:

public class CakeType { final int weight;

final int value; public CakeType(int weight, int value) {

this.weight = weight;

this.value = value;

}

}

You brought a duffel bag that can hold limited weight, and you want to make off with the most valuable haul possible.

Write a method maxDuffelBagValue() that takes **an array of cake type objects **and **a weight capacity**, and returns **the maximum monetary value the duffel bag can hold. Weights and values may be any non-negative integer.**

# Cracking the Coding Interview — Practice Question

## Qns 1: Leet code 70 Climbing stairs. You are climbing a stair case. It takes *n* steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

**Note:** Given *n* will be a positive integer.

Similar to coin change 2.

## Qns 2: Robots in a grid: A robot is located at the top-left corner of a *m* x *n* grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

## Extension 1 (Leet Code 63): Certain cells are marked off-boundary

## Extension 2 (Leet Code 980):

On a 2-dimensional `grid`

, there are 4 types of squares:

`1`

represents the starting square. There is exactly one starting square.`2`

represents the ending square. There is exactly one ending square.`0`

represents empty squares we can walk over.`-1`

represents obstacles that we cannot walk over.

Return the number of 4-directional walks from the starting square to the ending square, that **walk over every non-obstacle square exactly once**.

## Qns 2: Power Set -> Write a set to return all possible subset (Leet Code 78)

**Input:** nums = [1,2,3]

**Output:**

[

[3],

[1],

[2],

[1,2,3],

[1,3],

[2,3],

[1,2],

[]

]

Note that the solution below is wrong. In the solution below, List<> seems to be shared across different recursion functions. Even though in line 26, i appear to be modifying just duplicate list but i am actually modifying the original list. This is because, previously in line 21, i am adding the **d** from **list**. d is referring to the original list and we are directly modifying it.

At every recursion call:

- Add yourself
- Add yourself to all existing lists
- Add all existing lists

## Qns 3: Longest Increasing subsequence -> Can be non contiguous

## Extension Leetcode 673

Given an integer array `nums`

, return *the **number of longest increasing subsequences.*

**Notice** that the sequence has to be **strictly** increasing.

**Example 1:**

**Input:** nums = [1,3,5,4,7]

**Output:** 2

**Explanation:** The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7].

**Example 2:**

**Input:** nums = [2,2,2,2,2]

**Output:** 5

**Explanation:** The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.

Need to make sure that the two if statements are not swapped. This is because if we swapped them both, then the program will enter both if loops.

**Qns 4: Minimum path Sum**

Given a *m* x *n* grid filled with non-negative numbers, find a path from top left to bottom right which *minimizes* the sum of all numbers along its path.

**Note:** You can only move either down or right at any point in time.

**Example:**

**Input:**

[

[1,3,1],

[1,5,1],

[4,2,1]

]

**Output:** 7

**Explanation:** Because the path 1→3→1→1→1 minimizes the sum.

# Leetcode 1262. Greatest Sum Divisible by Three

Given an array `nums`

of integers, we need to find the maximum possible sum of elements of the array such that it is divisible by three.

**Example 1:**

**Input:** nums = [3,6,5,1,8]

**Output:** 18

**Explanation:** Pick numbers 3, 6, 1 and 8 their sum is 18 (maximum sum divisible by 3).

- dp[i,r] where r is the remainder and i is the end index of the number we are going to look at.
- We always start from index 0 and hence i is the end index.
- dp[i,r] will contain the max sum that gives the remainder r when we iterate from 0..i (inclusive).
- At every point of iterating through the num array, we have 2 choices: Do we include the current value or not?

- If we choose to include the current value, then we will have to calculate its’ remainder.
- To understand the equation better (Look at the comments below in my last appended code snippet).

=> dp[i,r]=max(A[i]+dp[i-1, (r-**A[i]**)%3], dp[i-1, r])

Even though it was written to be **A[i]**, i think it should not be **A[i]**.

## Leetcode discussion solution below:

## (The answer i derived from the above explanation) => **Look at this**

The above is the best answer.

# A question not found in Leet Code

Given a dictionary of words, each word has a positive score. Given a string, cut it to exactly K (K > 0) words and all of them must be found in the dictionary, and the word segmentation score is the sum of the K segmented word’s scores.

Return the max words segmentation score. If it is impossible, return -1.

Example 1:Input:[{“abc”, 1}, {“bcd”, 2}, {“f”, 7}], “abcbcdf”, 3Output:10 (segment “abcbcdf” to “abc”, “bcd”, “f”)

# Leet Code 10 Regular Expression Matching

Given an input string (`s`

) and a pattern (`p`

), implement regular expression matching with support for `'.'`

and `'*'`

where:

`'.'`

Matches any single character.`'*'`

Matches zero or more of the preceding element.

The matching should cover the **entire** input string (not partial).

**Example 1:**

**Input:** s = "aa", p = "a"

**Output:** false

**Explanation:** "a" does not match the entire string "aa".

**Example 2:**

**Input:** s = "aa", p = "a*"

**Output:** true

**Explanation:** '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

**Example 3:**

**Input:** s = "ab", p = ".*"

**Output:** true

**Explanation:** ".*" means "zero or more (*) of any character (.)".

**Example 4:**

**Input:** s = "aab", p = "c*a*b"

**Output:** true

**Explanation:** c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".

**Example 5:**

**Input:** s = "mississippi", p = "mis*is*p*."

**Output:** false

**Understanding what the symbols means:**

Consider what action to take when you encounter what character. Check out the following discussion for more:

- Firstly we
**initialise a 2D array**where the row is the pattern string and column vertically down is the string. - If we check that the
**current pattern character is the same as string character str[i] == pattern[j]**, then we go back 1 index for both and check if previously they were matching, str[0,1..i-1] == pattern[0,1…j-1]? This involves checking dp[i-1][j-1]. - If
**current pattern[j]==’.’**it means we can match the character j with any character in str[i]. Essentially, we can ignore the character at pattern[j] and str[i] and go back to check for match between str[0,1..i-1] and pattern[0,1…j-1]. This involves checking dp[i-1][j-1]. **If current pattern[j] == ‘*’**, we look at the previous character pattern[j-1] (for eg look at a if we have a*) and this can match with 0 or more elements with string[i]. So we compare them.- Case 1: If
, it will be the case where pattern[j-1, j] inclusive*pattern[j-1] != string[i]*. So we can treat pattern[j-1, j] to be removed , for eg remove a*, and go on to see if pattern[0,1…j-2] matches with string [0,1…i]. This will involve checking dp[i][j-2].*matches 0 elements* - If
or*pattern[j-1] == string[i]*, it can be that the pattern [j-1,j] matches either 0 or 1 or more elements in string.*pattern[j-1] == ‘.’ (for eg .*)* - Case 2: If it matches with ≥ 1 element, where we know that when pattern[j-1], a, matches with string[i], there is at least 1 character in S that matches with pattern[j-1], a. We then move backwards in string to check string[0,1…i-1] with pattern[0,1..j-1]. More specifically, we check if pattern[j-1], a, matches with string[i-1]. This involve checking dp[i-1][j-1].

Check out video for visualisation:

https://www.youtube.com/watch?v=l3hda49XcDE

# 801. Minimum Swaps To Make Sequences Increasing

We have two integer sequences `A`

and `B`

of the same non-zero length.

We are allowed to swap elements `A[i]`

and `B[i]`

. Note that both elements are in the same index position in their respective sequences.

At the end of some number of swaps, `A`

and `B`

are both strictly increasing. (A sequence is *strictly increasing* if and only if `A[0] < A[1] < A[2] < ... < A[A.length - 1]`

.)

Given A and B, return the minimum number of swaps to make both sequences strictly increasing. It is guaranteed that the given input always makes it possible.

**Example:**

**Input:** A = [1,3,5,4], B = [1,2,3,7]

**Output:** 1

**Explanation: **

Swap A[3] and B[3]. Then the sequences are:

A = [1, 3, 5, 7] and B = [1, 2, 3, 4]

which are both strictly increasing.

Leet Code Solution:

Line 12: swap at i-1 and i

Line 13: Don’t swap at i-1 and i

Line 17: Swap at i but don’t swap at i-1

Line 18: Swap at i-1 but don’t swap at i.

# Leet Code 221. Maximal Square

Given an `m x n`

binary `matrix`

filled with `0`

's and `1`

's, *find the largest square containing only* `1`

's *and return its area*.

**Example 1:**

**Input:** matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]

**Output:** 4

**Example 2:**

**Input:** matrix = [["0","1"],["1","0"]]

**Output:** 1

**Example 3:**

**Input:** matrix = [["0"]]

**Output:** 0

Hmmm hard to think that this is a dynamic programming question.

**Leet Code Suggested Solution**

We initialize another matrix (dp) with the same dimensions as the original one initialized with all 0’s.

**dp(i,j) represents the side length of the maximum square whose bottom right corner is the cell with index (i,j) in the original matrix.**

Starting from index (0,0), for every 1 found in the original matrix, we update the value of the current element as

We also remember the size of the largest square found so far. In this way, we traverse the original matrix once and find out the required maximum size. This gives the side length of the square (say maxsqlen). The required result is the area maxsqlen².

- Time complexity : O(mn). Single pass.
- Space complexity :
*O*(*mn*). Another matrix of same size is used for d.

# Leet Code 84 Largest Rectangle in Histogram

Given *n* non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = `[2,1,5,6,2,3]`

.

The largest rectangle is shown in the shaded area, which has area = `10`

unit.

**Example:**

**Input:** [2,1,5,6,2,3]

**Output:** 10

## Leet Code Discussion Solution:

We see that at every height[i], we want to compute the max possible rectangle formed. We want to expand from index i the furthest we can to the left and right direction. The stopping condition for the expansion is when we arrive at a height which is smaller than current height[i].

With this in mind, we then make use of 2 arrays indexLeft and indexRight. indexLeft[i] contains the first index on the left which has height < height[i]. The above illustration explains how to get the width of the rectangle. r-l+1.

# Leet Code 85 Maximal Rectangle (Similar to Maximal Squares)

Given a `rows x cols`

binary `matrix`

filled with `0`

's and `1`

's, find the largest rectangle containing only `1`

's and return *its area*.

**Example 1:**

**Input:** matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]

**Output:** 6

**Explanation:** The maximal rectangle is shown in the above picture.

**Example 2:**

**Input:** matrix = []

**Output:** 0

**Example 3:**

**Input:** matrix = [["0"]]

**Output:** 0

**Example 4:**

**Input:** matrix = [["1"]]

**Output:** 1

**Example 5:**

**Input:** matrix = [["0","0"]]

**Output:** 0

This question is similar to the previous question.

We can visualise each row as a histogram of bars. First, for each row, we construct this histogram of bars. The heights of a bar (column) in the histogram is the sum of the numbers in the current row and above for that column. For eg, see the image below.

Then, once we have a histogram for each rows constructed, we will then attempt to find the max rectangle for the histogram at each level. We apply the previous question technique to each row (1 histogram) and the final result would be the max rectangle formed from a histogram.

# Leet Code 42. Trapping Rain Water

Given `n`

non-negative integers representing an elevation map where the width of each bar is `1`

, compute how much water it can trap after raining.

**Example 1:**

**Input:** height = [0,1,0,2,1,0,1,3,2,1,2,1]

**Output:** 6

**Explanation:** The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

**Example 2:**

**Input:** height = [4,2,0,3,2,5]

**Output:** 9

# 51. N-Queens

The **n-queens** puzzle is the problem of placing `n`

queens on an `n x n`

chessboard such that no two queens attack each other.

Given an integer `n`

, return *all distinct solutions to the *** n-queens puzzle**.

Each solution contains a distinct board configuration of the n-queens’ placement, where `'Q'`

and `'.'`

both indicate a queen and an empty space, respectively.

**Example 1:**

**Input:** n = 4

**Output:** [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

**Explanation:** There exist two distinct solutions to the 4-queens puzzle as shown above

**Example 2:**

**Input:** n = 1

**Output:** [["Q"]]

We know for sure that when we have reached colIndex == board.length, all the rows have been filled. This is due to the validate function which ensures that a recursion call will not be called on a board that adds Q to the same row repeatedly. We only make new recursion call when Q is added to the next row. Hence, when colIndex == board.length, we know that board.length number of rows has been filled.

See that if we want to know if we can place Q in position (1,1), we will need its’ diagonals to be empty. So, when we are in the i,j position we want to check if the difference in magnitude in x-y direction from this (1,1) position is the same. If it is the same, we know that the current position i,j is in a diagonal position.

`x-i == y-j`

# Edit Distance between two strings is one (Not in leetcode)

An edit between two strings is one of the following changes.

- Add a character
- Delete a character
- Change a character

Given two string s1 and s2, find if s1 can be converted to s2 with exactly one edit. Expected time complexity is O(m+n) where m and n are lengths of two strings.

Examples:

Input: s1 = "geeks", s2 = "geek"

Output: yes

Number of edits is 1Input: s1 = "geeks", s2 = "geeks"

Output: no

Number of edits is 0Input: s1 = "geaks", s2 = "geeks"

Output: yes

Number of edits is 1Input: s1 = "peaks", s2 = "geeks"

Output: no

Number of edits is 2

We can classify into the different cases as seen in part 1 and then call the corresponding functions.

# 72. Edit Distance (Differerent from above)

Instead of just checking if they differ by 1 operation, now there can be >1 operations.

Given two strings `word1`

and `word2`

, return *the minimum number of operations required to convert **word1** to *

.*word2*

You have the following three operations permitted on a word:

- Insert a character
- Delete a character
- Replace a character

**Example 1:**

**Input:** word1 = "horse", word2 = "ros"

**Output:** 3

**Explanation:**

horse -> rorse (replace 'h' with 'r')

rorse -> rose (remove 'r')

rose -> ros (remove 'e')

**Example 2:**

**Input:** word1 = "intention", word2 = "execution"

**Output:** 5

**Explanation:**

intention -> inention (remove 't')

inention -> enention (replace 'i' with 'e')

enention -> exention (replace 'n' with 'x')

exention -> exection (replace 'n' with 'c')

exection -> execution (insert 'u')

Hence, we use dynamic programming.

# Leet Code 329. Longest Increasing Path in a Matrix

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

**Example 1:**

**Input: **nums =

[

[9,9,4],

[6,6,8],

[2,1,1]

]

**Output:** 4

**Explanation:** The longest increasing path is [1, 2, 6, 9].

**Example 2:**

**Input:** nums =

[

[3,4,5],

[3,2,6],

[2,2,1]

]

**Output: **4

**Explanation: **The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

# Leet Code 332. Reconstruct Itinerary

Given a list of airline tickets represented by pairs of departure and arrival airports `[from, to]`

, reconstruct the itinerary in order. All of the tickets belong to a man who departs from `JFK`

. Thus, the itinerary must begin with `JFK`

.

**Note:**

- If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary
`["JFK", "LGA"]`

has a smaller lexical order than`["JFK", "LGB"]`

. - All airports are represented by three capital letters (IATA code).
- You may assume all tickets form at least one valid itinerary.
**One must use all the tickets once and only once.**

**Example 1:**

**Input: **[["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]

**Output: **["JFK", "MUC", "LHR", "SFO", "SJC"]

**Example 2:**

**Input: **[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]

**Output: **["JFK","ATL","JFK","SFO","ATL","SFO"]

**Explanation: **Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"].

But it is larger in lexical order.

**Whenever each “Node” cannot be represented by a number, we use HashMap instead of an ArrayList.**

We use Recursion here.

WRONG SOLUTION 1: Using PriorityQueue

WRONG SOLUTION 2: Using stack

Hence, the best way is not to use Stack or Queue but to use Recursion. Using Stack or Queue does not enable us to discard nodes that were previously visited, but not supposed to be in the path.

Check out around 12 minute of this video

Run through of the algorithm on an example:

Each time you see a node, you will add it to the stack. When you find that you have reached a dead end, pop that single last element to the result list. Then, remove that element from the stack and continue.

Then, go on to N and then J. At N->J ticket, we see we have finished. So we pop from the stack.

The answer is in reversed order.

## Leet Code 38. Count and Say

The **count-and-say** sequence is a sequence of digit strings defined by the recursive formula:

`countAndSay(1) = "1"`

`countAndSay(n)`

is the way you would "say" the digit string from`countAndSay(n-1)`

, which is then converted into a different digit string.

To determine how you “say” a digit string, split it into the **minimal** number of groups so that each group is a contiguous section all of the **same character.** Then for each group, say the number of characters, then say the character. To convert the saying into a digit string, replace the counts with a number and concatenate every saying.

For example, the saying and conversion for digit string `"3322251"`

:

Given a positive integer `n`

, return *the *`nth`

* term of the **count-and-say** sequence*.

**Example 1:**

**Input:** n = 1

**Output:** "1"

**Explanation:** This is the base case.

**Example 2:**

**Input:** n = 4

**Output:** "1211"

**Explanation:**

countAndSay(1) = "1"

countAndSay(2) = say "1" = one 1 = "11"

countAndSay(3) = say "11" = two 1's = "21"

countAndSay(4) = say "21" = one 2 + one 1 = "12" + "11" = "1211"

# 698. Partition to K Equal Sum Subsets

Given an array of integers `nums`

and a positive integer `k`

, find whether it's possible to divide this array into `k`

non-empty subsets whose sums are all equal.

**Example 1:**

**Input:** nums = [4, 3, 2, 3, 5, 2, 1], k = 4

**Output:** True

**Explanation:** It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

# 416. Partition Equal Subset Sum

Given a **non-empty** array `nums`

containing **only positive integers**, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

**Example 1:**

**Input:** nums = [1,5,11,5]

**Output:** true

**Explanation:** The array can be partitioned as [1, 5, 5] and [11].

**Example 2:**

**Input:** nums = [1,2,3,5]

**Output:** false

**Explanation:** The array cannot be partitioned into equal sum subsets.

This question is similar to 0–1 Knapsack problem where you either choose a number or not.

Here, we attempt to form 1 subset which has the sum of SUM_OF_ALL_NUMS_ITEM/2.

# 198. House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and **it will automatically contact the police if two adjacent houses were broken into on the same night**.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight **without alerting the police**.

**Example 1:**

**Input:** nums = [1,2,3,1]

**Output:** 4

**Explanation:** Rob house 1 (money = 1) and then rob house 3 (money = 3).

Total amount you can rob = 1 + 3 = 4.

**Example 2:**

**Input:** nums = [2,7,9,3,1]

**Output:** 12

**Explanation:** Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).

Total amount you can rob = 2 + 9 + 1 = 12.

Solution:

This question smells strongly of DP.

# Leet Code 213 House Robber II

The question remains the same as above, except that all houses at this place are **arranged in a circle.**

## Solution:

Compute 2 times. We have 2 dps.

(1) The first dp is for when we include the first house. If we are at the last element, we decide whether to add last house value depending on whether first house value was used. If not used, then we can add. If used, then cannot add.

(2) The second dp is when we exclude the first house. Since we exclude it, then we can do the remaining dp method freely.

Then, we compare the two max values obtained.

# Leet Code 337. House Robber III

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

**Example 1:**

Input:[3,2,3,null,3,null,1] 3

/ \

2 3

\ \

3 1Output:7Explanation:Maximum amount of money the thief can rob = 3 + 3 + 1 =7.

**Example 2:**

Input:[3,4,5,1,3,null,1] 3

/ \

4 5

/ \ \

1 3 1Output:9Explanation:Maximum amount of money the thief can rob = 4 + 5 =9.

Use a helper function which receives a node and a bool variable as input, and **if that variable is false**, it **returns the maximum amount of money the thief can rob if starting from this node** and robbing this node, else returns the maximum amount of money the thief can rob if starting from this node without robbing this node.

# Leet Code 91 Decode Ways

A message containing letters from `A-Z`

can be **encoded** into numbers using the following mapping:

`'A' -> "1"`

'B' -> "2"

...

'Z' -> "26"

To **decode** an encoded message, all the digits must be mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, `"111"`

can have each of its `"1"`

s be mapped into `'A'`

s to make `"AAA"`

, or it could be mapped to `"11"`

and `"1"`

(`'K'`

and `'A'`

respectively) to make `"KA"`

. Note that `"06"`

cannot be mapped into `'F'`

since `"6"`

is different from `"06"`

.

Given a **non-empty** string `num`

containing only digits, return *the **number** of ways to **decode** it*.

The answer is guaranteed to fit in a **32-bit** integer.

**Example 1:**

**Input:** s = "12"

**Output:** 2

**Explanation:** "12" could be decoded as "AB" (1 2) or "L" (12).

**Example 2:**

**Input:** s = "226"

**Output:** 3

**Explanation:** "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

**Example 3:**

**Input:** s = "0"

**Output:** 0

**Explanation:** There is no character that is mapped to a number starting with 0. The only valid mappings with 0 are 'J' -> "10" and 'T' -> "20".

Since there is no character, there are no valid ways to decode this since all digits need to be mapped.

**Example 4:**

**Input:** s = "1"

**Output:** 1

This is similar to climb stairs problem.

TODO:

DECODE WAYS TWO

# 241. Different Ways to Add Parentheses

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are `+`

, `-`

and `*`

.

**Example 1:**

**Input:** "2-1-1"

**Output:** [0, 2]

**Explanation: **

((2-1)-1) = 0

(2-(1-1)) = 2

**Example 2:**

**Input: **"2*3-4*5"

**Output:** [-34, -14, -10, -10, 10]

**Explanation: **

(2*(3-(4*5))) = -34

((2*3)-(4*5)) = -14

((2*(3-4))*5) = -10

(2*((3-4)*5)) = -10

(((2*3)-4)*5) = 10

Solution:

- The key is to know that we do a split at every operator position. This problem is about different ways of slicing the expression string for k times where k is the number of operators. The different ways refers to the order in which they are sliced.

# 93. Restore IP Addresses

Given a string `s`

containing only digits, return all possible valid IP addresses that can be obtained from `s`

. You can return them in **any** order.

A **valid IP address** consists of exactly four integers, each integer is between `0`

and `255`

, separated by single dots and cannot have leading zeros. For example, "0.1.2.201" and "192.168.1.1" are **valid** IP addresses and "0.011.255.245", "192.168.1.312" and "192.168@1.1" are **invalid** IP addresses.

**Example 1:**

**Input:** s = "25525511135"

**Output:** ["255.255.11.135","255.255.111.35"]

**Example 2:**

**Input:** s = "0000"

**Output:** ["0.0.0.0"]

**Example 3:**

**Input:** s = "1111"

**Output:** ["1.1.1.1"]

**Example 4:**

**Input:** s = "010010"

**Output:** ["0.10.0.10","0.100.1.0"]

(Below is a related Qns but not recursion)

# 468. Validate IP Address

Given a string `IP`

, return `"IPv4"`

if IP is a valid IPv4 address, `"IPv6"`

if IP is a valid IPv6 address or `"Neither"`

if IP is not a correct IP of any type.

**A valid IPv4** address is an IP in the form `"x1.x2.x3.x4"`

where `0 <= xi <= 255`

and `xi`

**cannot contain** leading zeros. For example, `"192.168.1.1"`

and `"192.168.1.0"`

are valid IPv4 addresses but `"192.168.01.1"`

, while `"192.168.1.00"`

and `"192.168@1.1"`

are invalid IPv4 addresses.

**A valid IPv6** address is an IP in the form `"x1:x2:x3:x4:x5:x6:x7:x8"`

where:

`1 <= xi.length <= 4`

`xi`

is a**hexadecimal string**which may contain digits, lower-case English letter (`'a'`

to`'f'`

) and upper-case English letters (`'A'`

to`'F'`

).- Leading zeros are allowed in
`xi`

.

For example, “`2001:0db8:85a3:0000:0000:8a2e:0370:7334"`

and "`2001:db8:85a3:0:0:8A2E:0370:7334"`

are valid IPv6 addresses, while "`2001:0db8:85a3::8A2E:037j:7334"`

and "`02001:0db8:85a3:0000:0000:8a2e:0370:7334"`

are invalid IPv6 addresses.

# 943. Find the Shortest Superstring

https://leetcode.com/problems/find-the-shortest-superstring/

Given an array of strings `words`

, return *the smallest string that contains each string in* `words`

*as a substring*. If there are multiple valid strings of the smallest length, return **any of them**.

You may assume that no string in `words`

is a substring of another string in `words`

.

**Example 1:**

**Input:** words = ["alex","loves","leetcode"]

**Output:** "alexlovesleetcode"

**Explanation:** All permutations of "alex","loves","leetcode" would also be accepted.

**Example 2:**

**Input:** words = ["catg","ctaagt","gcta","ttca","atgcatc"]

**Output:** "gctaagttcatgcatc"