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

\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}



\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{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}