Skip to content

Latest commit

 

History

History
40 lines (33 loc) · 1.31 KB

backtracking.md

File metadata and controls

40 lines (33 loc) · 1.31 KB
Raw

backtracking

intro

  • backtracking like dfs on a tree
  • if a problem need try and error (make decisions) to enum every res, then use backtracking
    • making decisions
      • each round we got multi choices (must pick one)
      • each round we choose sth or not choose
    • notice elements are duplicate or unique
      • if so, we need to take care of pruning
    • notice elements can be chosen repeatedly or not
      • if not, we need to maintain a memo
    • notice that inside backtracking, we can use the boolean value as a return value to indicate whether there is a valid answer or not
def backtrack(res, path, count, visited, index/node):
    if BOUND_REACHED:
        if GOAL_REACHED:
            RECORD_RESULT
        return

    for CHOCIE in CHOICES:
        if CHOICE is VALID:
            MAKE_CHOICE
            backtrack(res, path, count, visited, index/node)
            UNDO_CHOICE

pattern

  • subset
    • a subset is composed of none or some or all elements from a set
  • permutation
    • a permutation is an ordered selection of a certain number of elements from a set
  • combination
    • a combination is an unordered selection of a certain number of elements from a set
  • backtracking with constraints
    • make choices and backtrack based on certain constraints or conditions