Backtracking

题目列表

  • permutation
  • subsets
  • generate parentheses
  • ...

Complexity analysis of recursion

Exmaple Factorial

assume each simple operation is unit 1

def factorial(n):
    if n == 0:
        return 1 # 1
    else:
        return n * factorial(n-1) # 1 + 1

So time conplexity: 

T(n) = T(n-1) + 3
        = T(n-2) + 6
        = T(n-k) + 3k
k -> n
T(n) = T(0) + 3n = 3n + 1

space complexity

Recursion Tree F(5) -> F(4) # saves F(5) in memory F(4) -> F(3) # saves F(4) in memory ...

states of function calls are stacked in the memory, Implicit stack. recursion tree max-depth is 5. space complexity is O(n)

Fibonacci

def fib(n):
    if n <= 1:
        return n # 1
    else:
        return fib(n-1) + fib(n-2) # 1 + 1 + 1

T(n) = T(n-1) + T(n-2) + 4

We need to do some approximation.

Lower Bound

Let's assume T(n-1) = T(n-2), cause in reality T(n-1) >= T(n-2), so it's lower bound.

T(n) = 2T(n-2) + C
        = 2(2T(n-4)+C) + C = 4T(n-4) + 3C
        = 8T(n-6) + 7C
        = 2^k * T(n-2k) + (2^k - 1)C
# we know T(0) is constant
k = n/2
T(n) = 2^(n/2) * T(0) + (2^(n/2)-1)C
        = (1 + C) * 2^(n/2) - C  # lower bound

Upper bound

Let's assume T(n-2) = T(n-1)

T(n) = 2T(n-1) + C
        = 2^k * T(n-k) + (2^k - 1) * C
        = (1 + C) * 2^k - C

upper bound O(2^n)

backtracking intro

Backtracking is trying out all possibilities using recursion, exactly like bruteforce.

Suppose you have to make a series of decisions, among various choices, where

  • you don't have enought inforo to konw what to choose
  • each decision leads to a new set of choices
  • some sequence of choices may be a solution to your problem

Backtraking is a methodical way of trying out various sequences of decisions, until you find one that "works".

So, you explore each option thoroughly and once you cannot find a solution using the option selected, you come back and try one of the remaining options.

general pseudocode

boolean solve(Node n){
    if n is a goal node, return true

    foreach option o possible from n {
        if solve(o) succeeds, return true
    }
    return false
}

问题描述

所谓Backtracking大都是这样的思路：

  1. 当前局面下，你有若干种选择，那么尝试每一种选择。
  2. 如果发现某种选择一家肯定不行，就返回
  3. 如果某种选择试到最后能发现是正确的，就将其加入解

所以思考递归题的时候，只要明确三点就可以：

  1. 选择
  2. 限制
  3. 结束条件

比如 generate parentheses的例子。

  1. 选择

在任何时刻，有两种选择：

  • 加左括号

  • 加右括号

  • 限制

  • 左括号用完了，不能再加左括号

  • 右括号已经和左括号一样多，不能再加右括号

  • 结束条件

左右括号都用完了，就可以加入最终记过的list。

递归函数的传入参数

根据限制和结束条件来定，所以需要知道左右括号的数量，当然还有curList和 results list.

Reference