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{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))
        return

    if (i >= len(A) or len(cur) > k 
        or len(A)-i+len(cur) < k):
        return

    self.dfs(A, i+1, k, cur, remain, ret)
    cur.append(A[i])
    self.dfs(A, i+1, k, cur, remain-A[i], ret)
    cur.pop()
\end{python}


\section{String}
\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))

    for i in xrange(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 xrange(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}

\section{Math}
\subsection{Decomposition}
\subsubsection{Factorize a number}\label{factorization}
\runinhead{Core clues:}
\begin{enumerate}
\item Expand the search tree \textbf{horizontally}.
\end{enumerate}
\runinhead{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}
Code:
\begin{python}
def dfs(self, cur, ret):
  if len(cur) > 1:
    ret.append(list(cur))

  n = cur.pop()
  start = cur[-1] if cur else 2
  for i in xrange(start, int(sqrt(n))+1):
    if self.predicate(n, i):
      cur.append(i)
      cur.append(n/i)
      self.dfs(cur, ret)
      cur.pop()
            
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, 
        cur_str, cur_val, 
        mul, ret
):
  if pos >= len(num):
    if cur_val == target:
      ret.append(cur_str)
  else:
    for i in xrange(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, 
            "%d"%nxt_val, nxt_val,
            nxt_val, ret)
      else:  # +, -, *
        self.dfs(num, target, i+1, 
            cur_str+"+%d"%nxt_val, cur_val+nxt_val, 
            nxt_val, ret)
        self.dfs(num, target, i+1, 
            cur_str+"-%d"%nxt_val, cur_val-nxt_val, 
            -nxt_val, ret)
        self.dfs(num, target, i+1, 
    cur_str+"*%d"%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 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, rmcnt = 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):
  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)
        root.left = left_root
        root.right = right_root

        roots.append(root)

  return roots 

\end{python}