chapterBacktracking.tex

\chapter{Backtracking}
\section{Introduction}
\runinhead{Difference between backtracking and dfs.} \textit{Backtracking} is a more general purpose algorithm. \textit{Dfs} is a specific form of backtracking related to searching tree structures. 

\runinhead{Prune.} Backtrack need to think about pruning using the condition \pyinline{predicate}.

\runinhead{Jump.} Jump to skip ones the same as its parent to avoid duplication.

\runinhead{Complexity.} $O(b^d)$, where $b$ is the branching factor and $d$ is the depth. 


\section{Memoization}
dfs can be memoized.
\begin{python}
import functools

@functools.lru_cache(maxsize=None)
def dfs(self, *args):
  pass
\end{python}
\section{Sequence}
\runinhead{k sum.} Given $n$ unique integers, number $k$ and target. Find all possible $k$ integers where their sum is target. 

Complexity: $O(2^n)$.

Pay attention to the pruning condition.

\begin{python}
def dfs(self, A, i, k, cur, remain, ret):
    """self.dfs(A, 0, k, [], target, ret)"""
    if len(cur) == k and remain == 0:
        ret.append(list(cur))  # clone 
        return

    if i >= len(A) or len(cur) > k 
       or len(A) - i + len(cur) < k:
        return
	
	# not select 
    self.dfs(A, i+1, k, cur, remain, ret)
    
    # select
    cur.append(A[i])
    self.dfs(A, i+1, k, cur, remain-A[i], ret)
    cur.pop()
\end{python}


\section{String}
In general, 
\begin{itemize}
\item Break down the sequence into \pyinline{left} and \pyinline{right} two parts. 
\item Choose \pyinline{left} as terminal state, while DFS search the \pyinline{right}. 
\item Combine \pyinline{left} and the search results from \pyinline{right}.
\item Sometimes it is easier to search \pyinline{left} and choose \pyinline{right} as terminal state. 
\end{itemize}
\subsection{Palindrome}
\subsubsection{Palindrome partition.} Given \pyinline{s = "aab"}, return: \\
\pyinline{[["aa","b"], ["a","a","b"]]}
\\
\runinhead{Core clues:}
\begin{enumerate}
\item Expand the search tree \textbf{horizontally}.
\end{enumerate}
\rih{Search process:}
\begin{python}
input: "aabbc"

"a", "abbc"
     "a", "bbc"
          "b", "bc"
               "b", "c" (o)
               "bc" (x)
          "bb", "c" (o)
          "bbc" (x)
     "ab", "bc" (x)
     "abb", "c" (x)
     "abbc" (x)
"aa", "bbc"
      "b", "bc"
           "b", "c" (o)
           "bc" (x)
      "bb", "c" (o)
      "bbc" (x)
"aab", "bc" (x)
"aabb", "c" (x)
\end{python}
Code:

\begin{python}
def partition(self, s):
    ret = []
    self.backtrack(s, [], ret)
    return ret

def backtrack(self, s, cur_lvl, ret):
    """
    Let i be the scanning ptr.
    If s[:i] passes predicate, then backtrack s[i:]
    """
    if not s:
        ret.append(list(cur_lvl))  # clone

    for i in range(1, len(s)+1):
        if self.predicate(s[:i]):
            cur_lvl.append(s[:i])
            self.backtrack(s[i:], cur_lvl, ret)
            cur_lvl.pop()

def predicate(self, s):
    return s == s[::-1]
\end{python}

\subsection{Word Abbreviation}
\runinhead{Core clues:}
\begin{enumerate}
\item Pivot a letter
\item Left side as a number, right side dfs 
\end{enumerate}

\begin{python}
def dfs(self, word):
    if not word:
        yield ""

    for l in range(len(word)+1):
        left_num = str(l) if l else ""
        for right in self.dfs(word[l+1:]):
            yield left_num + word[l:l+1] + right
            # note word[l:l+1] and right default ''
\end{python}

\subsection{Split Array - Minimize Maximum Subarray Sum}
Split the array into $m$ parts and minimize the max subarray sum.
\runinhead{Core clues:}
\begin{enumerate}
\item Take one subarray from left, and search the right side for the minimum max subarray. 
\item To make process in the DFS, always make the left part a subarray, and DFS the right part. 
\item Pivot an index to break the array into the left and right parts.
\end{enumerate}

Search right.
\begin{python}
def dfs(self, cur, m):
    """
    * p break the nums[cur:] into left and right part
    * sums is the prefix sum (sums[i] == sum(nums[:i]))
    """
    if m == 1:
        return self.sums[len(nums)] - self.sums[cur]

    mini = float("inf")
    for j in range(cur, lens(nums)):
        left = self.sums[j + 1] - self.sums[0]
        right = self.dfs(j + 1, m - 1)
        # minimize the max
        mini = min(mini, max(left, right))

    return mini
\end{python}

Alternatively, search left. 
\begin{python}
def dfs(self, hi, m):
    """
    j break the nums[:hi] into left and right part
    sums is the prefix sum (sums[i] == sum(nums[:i]))
    """
    if m == 1:
        return self.sums[hi] - self.sums[0]

    mini = float("inf")
    for j in range(hi):
        right = self.sums[hi] - self.sums[j]
        left = self.dfs(j, m - 1)
        # minimize the max
        mini = min(mini, max(left, right))

    return mini
\end{python}


\section{Cartesian Product}
Each state can generate multiple combinations. Search through all the combinations.
\subsection{Pyramid Transition Matrix.}
\begin{python}
"""
 (H, I ..)
   / \
(D,E) (F, G)
 / \ / \
A   B   C
"""
def dfs(
    self, 
    T: Dict[Tuple[str, str], Set[str]], 
    level: str,
) -> bool:
    """
    T - Transition matrix
    stores all the possible end states from state1 
    and state2
    [s1, s2] -> set of end states 
    """
    if len(level) == 1:
        return True

    for nxt_level in itertools.product(
        *[T[a, b] for a, b in zip(level, level[1:])]
    ):
        if self.dfs(T, nxt_level):
            return True

    return False

\end{python}


\section{Math}
\subsection{Decomposition}
\subsubsection{Factorize a number}\label{factorization}
\runinhead{Core clues:}
\begin{enumerate}
\item Expand the search tree \textbf{horizontally}.
\item Take the last number on the stack, and factorize it recursively.
\end{enumerate}
\rih{Search tree:}
\begin{python}
Input: 16
get factors of cur[-1]
[16]
[2, 8]
[2, 2, 4]
[2, 2, 2, 2]

[4, 4]
\end{python}
Take the last number from the list and factorize it.

Code:

\begin{python}
ret = []  # collector

def dfs(cur, remain, ret):
  if remain == 1:
    res.append(list(cur))
    return
        
  start = 2 if not cur else cur[-1]
  # if start = 2, it generates duplicate combinations
  for factor in range(start, remain + 1):
    if remain % factor == 0:
      dfs(cur + [factor], remain // factor)

dfs([], target, ret)
\end{python}

Using a single stack to conserve space, we need to maintain the stack \pyinline{cur}. 
\begin{python}
self.dfs([16], [])

def dfs(self, cur, ret):
  if len(cur) > 1:
    ret.append(list(cur))  # clone 

  n = cur.pop()
  start = cur[-1] if cur else 2
  for i in range(start, int(sqrt(n))+1):
    if self.predicate(n, i):
      cur.append(i)
      cur.append(n // i)
      self.dfs(cur, ret)
      cur.pop()  # pop the i here. pop n // i in dfs
            
def predicate(self, n, i):
  return n % i == 0
  
\end{python}
\runinhead{Time complexity.} The search tree's size is $O(2^n)$ where $n$ is the number
of prime factors. Choose $i$ prime factors to combine then, and keep the rest uncombined.


$$\sum_i {n \choose i} = 2^n$$

\section{Arithmetic Expression}
\subsection{Unidirection}
\rih{Insert operators.} Given a string that contains only digits 0-9 and a target value,
return all possibilities to add binary operators (not unary) +, -, or * between the
digits so they evaluate to the target value.

Example: 
\begin{align*}
``123", 6 \rightarrow [``1+2+3", ``1*2*3"] \\ 
``232", 8 \rightarrow [``2*3+2", ``2+3*2"] \\
\end{align*}
Clues:
\begin{enumerate}
\item Backtracking with \textit{horizontal} expanding
\item Special handling for multiplication - caching the expression \textit{predecessor}
for multiplication association. 
\item Detect \textit{invalid} number with leading 0's
\end{enumerate}

\begin{python}
def addOperators(self, num, target):
  ret = []
  self.dfs(num, target, 0, "", 0, 0, ret)
  return ret

def dfs(
    self, 
    num, 
    target, 
    pos,  # scanning index 
    cur_str,  # The current str builder 
    cur_val,  # To reach the target 
    mul,  # first operand for multiplication 
    ret,
):
  if pos >= len(num):
    if cur_val == target:
      ret.append(cur_str)
  else:
    for i in range(pos, len(num)):
      if i != pos and num[pos] == '0':
        continue
        
      nxt_val = int(num[pos:i+1])
      if not cur_str:  # 1st number
        self.dfs(num, target, i+1, 
            f"nxt_val", nxt_val,
            nxt_val, ret)
      else:  # +, -, *
        self.dfs(num, target, i+1, 
            f"{cur_str}+{nxt_val}", cur_val+nxt_val, 
            nxt_val, ret)
        self.dfs(num, target, i+1, 
            f"{cur_str}-{nxt_val}", cur_val-nxt_val, 
            -nxt_val, ret)
        self.dfs(num, target, i+1, 
    f"{cur_str}*{nxt_val}", cur_val-mul+mul*nxt_val, 
            mul*nxt_val, ret)
\end{python}
\subsection{Bidirection}
\rih{Insert parenthesis.} 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 *.

Examples:
\begin{align*}
(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
\end{align*}
Clues: Iterate the operators, divide and conquer - left parts and right parts and then
combine result. \\
Code:
\begin{python}
def dfs_eval(self, nums, ops):
  ret = []
  if not ops:
    assert len(nums) == 1
    return nums

  for i, op in enumerate(ops):
    left_vals = self.dfs_eval(nums[:i+1], ops[:i])
    right_vals = self.dfs_eval(nums[i+1:], ops[i+1:])
    for l in left_vals:
      for r in right_vals:
        ret.append(self._eval(l, r, op))

  return ret
\end{python}
\section{Parenthesis}
\runinhead{Remove Invalid Parentheses.} Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Core clues:
\begin{enumerate}
\item \textbf{Backtracking}: All possible results $\ra$ backtrack. 
\item \textbf{Minrm}: Find the minimal number of removal.
\item \textbf{Jump}: To avoid duplicate, remove all brackets same as previous one $\pi$ at once.
\end{enumerate}

To find the minimal number of removal:
\begin{python}
def minrm(self, s):
    """
    returns minimal number of removals
    """
    rmcnt = 0
    left = 0
    for c in s:
        if c == "(":
            left += 1
        elif c == ")":
            if left > 0:
                left -= 1
            else:
                rmcnt += 1

    rmcnt += left
    return rmcnt
\end{python}
To return all possible results, do backtracking: 
\begin{python}
def dfs(self, s, cur, left, pi, i, rmcnt, ret):
  """
  Remove parenthesis
  backtracking, post-check
  :param s: original string
  :param cur: current string builder
  :param left: number of remaining left parentheses in s[0..i]
  :param pi: last removed char
  :param i: current index
  :param rmcnt: number of remaining removals needed
  :param ret: results
  """
  if left < 0 or rmcnt < 0 or i > len(s):
    return
  if i == len(s):
    if rmcnt == 0 and left == 0:
      ret.append(cur)
    return

  if s[i] not in ("(", ")"):  # skip non-parenthesis
    self.dfs(s, cur+s[i], left, None, i+1, rmcnt, ret)
  else:
    if pi == s[i]:
      while i < len(s) and pi and pi == s[i]: 
        i += 1
        rmcnt -= 1
      self.dfs(s, cur, left, pi, i, rmcnt, ret)
    else:
      self.dfs(s, cur, left, s[i], i+1, rmcnt-1, ret)
      L = left+1 if s[i] == "(" else left-1  # consume "("
      self.dfs(s, cur+s[i], L, None, i+1, rmcnt, ret)  # not rm
\end{python}
\section{Tree}
\subsection{BST}
\subsubsection{Generate Valid BST}
Generate all valid BST with nodes from 1 to $n$.
\runinhead{Core clues:}
\begin{enumerate}
\item Iterate pivot
\item Generate left and right
\end{enumerate}
Code:
\begin{python}
def generate(self, start, end) -> List[TreeNode]:
  roots = []
  if start > end:
    roots.append(None)
    return roots

  for pivot in range(start, end+1):
    left_roots = self.generate_cache(start, pivot-1)
    right_roots = self.generate_cache(pivot+1, end)
    
    for left_root in left_roots:
      for right_root in right_roots:
        root = TreeNode(pivot)  # new instance
        root.left = left_root
        root.right = right_root

        roots.append(root)

  return roots 

\end{python}