算法

[yozyyyqls]

[yozyyyqls]

Backtracking Blueprint:

1. Choice: Defining Our Decision Space

   The choice is the core choice we are making at each step.
   For example: fill the cell with a number.

2. Constraints: Directing Our Recursion

   Validate each choice to make sure they follow the rule.

3. Goal: When Recursion Bottoms Out

   The goal is the base case. When we reach out to the base case, we will stop recursing.

[yozyyyqls]

Recursion

1. The base case.
2. What is the return value of each recursive function?
3. What to do with the return value?
4. What is the operation in the current recursive function?

[yozyyyqls]

Backtracking Blueprint:

1. Choice: Defining Our Decision Space
   The choice is the core choice we are making at each step.
   For example: fill the cell with a number.
2. Constraints: Directing Our Recursion
   Validate each choice to make sure they follow the rule.
3. Goal: When Recursion Bottoms Out
   The goal is the base case. When we reach out to the base case, we will stop recursing.

How to analyze the time complexity of backtracking?

THEOREM 1

There are at most m^h leaves in an m-ary tree of height h.

THEOREM 2

l leaves has n = (ml -1)/(m - 1) vertices.

Then draw the recursive tree and use the two theories above to compute the maximum number of vertices of the tree.

[yozyyyqls]

Backtracking Blueprint:

1. Choice: Defining Our Decision Space
   The choice is the core choice we are making at each step.
   For example: fill the cell with a number.
2. Constraints: Directing Our Recursion
   Validate each choice to make sure they follow the rule.
3. Goal: When Recursion Bottoms Out
   The goal is the base case. When we reach out to the base case, we will stop recursing.

The Difference Between Backtracking and Brute Force Approach

• In Brute Force: You generate all the possible combinations you can and then check if any of them is valid.
• In Backtracking: In each step, you check if this step satisfied all the conditions
  • If it does: You continue generating the subsequent solutions.
  • If it does not: You go back to the previous step and check for another path.