This is the 9th day of my participation in Gwen Challenge

Recursion and backtracking are closely related:

  • The basic nature of recursion is function call. When dealing with problems, recursion is often the process of making a large problem smaller and then deducing it.

  • Backtracking is a process of making use of the nature of recursion to start from the starting point of the problem, keep trying, go back one step or even several steps, and then make choices until finally reaching the end point.

Recursion

Algorithm thought

A recursive algorithm is an algorithm that calls its own function (many properties of binary trees are recursive by definition).

For example :(hannott’s tower problem) there are three towers A, B, and c. at the beginning, n plates are placed on tower A in bottom-up order from largest to smallest. Now I’m asking you to move all the plates from Tower A to Tower C and have you print out the moving steps. Only one plate may be carried at a time, and no large plate may be placed on top of small plates at any time, no matter which tower it is on.

Solution:

  • From the final result, to stack n plates in order of size on tower C, you need to move the largest plate from the bottom of tower A to tower C;

  • To achieve step 1, place all but the largest plate on tower B.

It can be seen from the above that the original problem scale is changed from N plates to N-1 plates, that is, n-1 plates are transferred to tower B.

If A function can move n dishes from tower A to tower C, with the help of tower B. So, you can also use this function to move n minus 1 dishes from tower A, and with the help of tower C, to tower B. Similarly, keep reducing the size of the problem, and when n is 1, there is only 1 plate, just print out the steps.

Code:

void hano(char A, char B, char C, int n) {
    if (n > 0) {
        hano(A, C, B, n - 1);
        move(A, C);
        hano(B, A, C, n - 1); }}Copy the code

The recursive algorithm idea is summarized from the above. The scale of a problem is reduced, and then the final result is obtained by using the results obtained from the small-scale problem and combining the current value or situation.

In layman’s terms, the recursive function that you want to implement is considered to have been implemented, you just solve some subproblems, and then you need to think about how to get the answer based on the solution of the subproblem and the situation that you are facing. This algorithm is also known as a top-down algorithm.

LeetCode 91, the method of decoding.

A message containing the letters A-Z is encoded as follows:

‘A’ -> 1

‘B’ -> 2

…

‘Z’ -> 26

Given a non-empty string containing only numbers, count the total number of decoding methods.

Their thinking

In the second example, given that the encoded message is the string “226”, if there are m possible decoding possibilities for “22”, adding an extra “6” at the end is equivalent to adding an extra “F” character to the final decrypted string, and the total number of decoding possibilities is still only M.

For “6”, if it is preceded by “1” or “2”, it may be “16” or “26”, so it can look further back and find “26”. And the previous decoding combination is K, so in the k solved codes, add a “Z”, so the total number of decoding is M + K.

Code implementation

int numDecodings(String s) {

    if (s.charAt(0) = ='0')
        return 0;

    char[] chars = s.toCharArray();
    return decode(chars, chars.length - 1);
}

// The string is converted to an array of characters, using the recursive function decode, recursing from the last character forward
int decode(char[] chars, int index) {
    // There is only one decoding method for the first character, which returns 1
    if (index <= 0) return 1;
        
    int count = 0;
        
    char curr = chars[index];
    char prev = chars[index - 1];
   
    // If the current character is larger than "0", the result of the preceding string is used directly
    if (curr > '0') {
        count = decode(chars, index - 1);
    }
   
    // A number consisting of the previous character and the current character. The value must be between 1 and 26, otherwise it cannot be decoded
    if (prev == '1' || (prev == '2' && curr <= '6')) {
        count += decode(chars, index - 2);
    }
        
    return count;
}
Copy the code

Solution template Through the above examples, to summarize the recursive function solution template.

The problem solving steps

  • This step, also known as a Sanity Check, is to determine whether the current situation is illegal, and if it is, to return immediately. For example, see if the current situation is out of bounds and if a condition is not met. Usually, this part of the code is written first.

  • Determine whether the conditions for ending recursion are met. In this step, we’re basically dealing with the initial cases that were defined in the derivation.

  • Reduce the size of the problem and recursively call. In merge sort and quicksort, we reduced the size of the problem by half, and in the hannotta and decode example, we reduced the size of the problem by one.

  • Use the answers in small-scale questions and integrate them with current data to get the final answer.

Code implementation

function fn(n) {
    // Step 1: Check whether the input or status is illegal.
    if (input/state is invalid) {
        return;
    }

    // Step 2: Should the recursion end?
    if (match condition) {
        return some value;
    }

    // Step 3: Reduce the problem size
    result1 = fn(n1)
    result2 = fn(n2)
    ...

    // Step 4: Integrate the results
    return combine(result1, result2)
}
Copy the code

Find all centrosymmetric numbers of length N.

The sample

Enter: n = 2

Output: [” 11 “, “69”, “88”, “96”]

Their thinking

  • When n=0, the empty string “” should be printed.

  • When n=1, the centrosymmetric numbers of length 1 are: 0,1,8.

  • When n=2, the centrosymmetric numbers of length 2 are: 11, 69,88,96. Note: 00 is not a legal result.

  • When n is equal to 3, you just keep adding 11,69,88,96 to both sides of the legal centrosymmetric number of length 1.

[101, 609, 808, 906, 111, 619, 818, 916, 181, 689, 888, 986]

As n grows, all we need to do is add 11,69,88,96 to the centrosymmetric numbers of length n minus 2.

Code implementation

List<String> helper(int n, int m) {
    // Step 1: Check whether the input or status is illegal.
    if (n < 0 || m < 0 || n > m) {
        throw new IllegalArgumentException("invalid input");
  }

    // Step 2: Should the recursion end?
    if (n == 0) return new ArrayList<String>(Arrays.asList(""));
    if (n == 1) return new ArrayList<String>(Arrays.asList("0"."1"."8"));
  
    // Step 3: Reduce the problem size
    List<String> list = helper(n - 2, m); 

    // Step 4: Integrate the results
    List<String> res = new ArrayList<String>();
  
    for (int i = 0; i < list.size(); i++) {
        String s = list.get(i);
    
        if(n ! = m) res.add("0" + s + "0");
    
        res.add("1" + s + "1");
        res.add("6" + s + "9");
        res.add("8" + s + "8");
        res.add("9" + s + "6");
    }
  
    return res;
}
Copy the code

Algorithm analysis

Analysis non-recursive algorithm’s time complexity is very directly, and the time complexity of bubble sort, insertion sort, for example, layer analysis method is to count how many cycle, because each layer inside the loop execution of operations are compared and the exchange, the time complexity is O (1), so, the final time complexity is to cycle is multiplied by the length of each layer.

Two methods are recommended for analysis recursion algorithm:

  • Iterative method

  • Formula method

Iterative method example: Analyze the time complexity of hannotta recursive function.

void hano(char A, char B, char C, int n) {
    if (n > 0) {
        hano(A, C, B, n - 1);
        move(A, C);
        hano(B, A, C, n - 1); }}Copy the code

Let’s say that the running time of this recursive function is T(n).

  1. If statement (generally take if block or else block maximum time complexity), compare and determine the size of n, CPU execution time is 1 unit.

  2. Two calls to the recursive function, each time reducing the size of the problem by 1, get twice T(n-1). The CPU execution time of printed statements is also 1 unit. So T(n) = 1 + 2×T(n-1) + 1.

Here, the execution time of the if statement and print-out statement has nothing to do with the problem size N, so their algorithm time complexity can be written as O(1), and the expression becomes: T(n) = 2×T(n-1) + O(1).

When n=0, T(0) = 1, because when there are no dishes, the if statement also does a comparison to see if n is greater than 0.

  1. Expand T(n) by iteration.

T(n-1) = 2×T(n-2) + 1, and so on, continuously substituted into the expression of T(n), the following relationship can be obtained:

T (n) = 2 * (2 * T (n – 2) + 1) + 1 = 22 x T (n – 2) + (2 + 1)

T (n) = 2 * (2 * (2 * T (n – 3) + 1) + 1) + 1 = 23 * T (n – 3) + (4 + 2 + 1)

T (n) = 2 * (2 * (2 * (2 * T (n – (4) + 1) + 1) + 1) + 1 = 24 T (n – (4) + x (8 + 4 + 2 + 1)

…

T of n is equal to 2k times T of n-k plus 2k minus 1.

1 + 2 + 4 + 8 +… It’s a geometric sequence, and the sum formula gives you 2k minus 1. When k is equal to n, T of n is equal to 2n times T of 0 plus 2n minus 1, because T of 0 is 1, so T of n is equal to 2 times 2n minus 1.

The value of O for T(n) is: O(n) = O(T(n)) = O(2× 2n-1), ignoring constants and coefficients, O(n) = O(2n).

So, the time of the whole algorithm is O(2n).

When it is difficult to deduce the complex time complexity through iterative method, formula method can be used.

Formula method

The formula method can be said to be the most convenient tool to calculate the complexity of recursive functions. When the time execution function of recursive functions meets the following relationship, we can use the formula method: T(n) = a×T(n/b) + f(n).

Where, f(n) is the extra computation execution time after each recursive completion. For example, in merge sort, we need to merge the two arrays each time we recursively process them, so the execution time of this operation is f(n).

When the parameters a and B are determined, just look at the recursion part, its time complexity is O(n^logba).

Since the time complexity is the upper bound, the overall time complexity is obtained by comparing the relationship between the time complexity of the recursive part and the size of f(n). Keep these three situations and formulas in mind:

  • When nlog(b)a is greater than f(n), the final time is O(n^logba).

  • When the execution time of the recursive part is less than f(n), the final time complexity is f(n).

  • When the execution time of the recursive part is nlog(b)a equals f(n), the final time is order (n^logba)logn.

Example 1: Analyze the time complexity of merge sort.

T(n) = 2T(n/2) + n

A = 2, b = 2, f(n) = n

Log of ba = 1, n1 = n

In the third case, the final time is O(nlogn).

Example 2: Analyze the time complexity of the following functions.

int recursiveFn(int n) {
    if (n == 0) {
        return 0;
    }
    return recursiveFn(n / 4) + recursiveFn(n / 4);
}
Copy the code

The time execution function: T(n) = 2×T(n/4) + 1, a = 2, b = 4, f(n) = 1.

Substitute into the formula: n^log42 = N0.5, when n>1, N0.5 >1, therefore, the time complexity is O(n0.5).

Example 3: Run the following function to analyze the time complexity.

T of n is equal to 3 times T of n over 2 plus n2

A = 3, b = 2, f(n) = n2

The most complex operations occur after the recursion is complete, which fits the second case.

Substitute the formula to get: n^log23 = N1.48 <n2, the time complexity of the final recursion is O(n2).

Summary for the analysis of time complexity is a very important part of the algorithm interview, master the iterative method and formula method, for the analysis of most interview questions are very important help, need to continue to practice, to skillfully use them.

Backtracking

Backtracking algorithm thought, in fact, a kind of heuristic algorithm, this algorithm to search the biggest difference is that violence, in the backtracking algorithm is forward to test step by step carefully, every step to detect, evaluate if the situation has been unable to meet the requirements, then there is no need to proceed, that is to say, It can help us avoid many detours.

The characteristic of backtracking algorithm is that when an illegal situation occurs, the algorithm can go back to the previous situation, which can be one step back, sometimes even multiple steps back, and then try other paths and methods. This means that if you want to use backtracking, you have to make sure that there are multiple attempts at each time.

The problem solving steps

  • Determine whether the current situation is illegal and return immediately if it is.

  • Whether the current situation has met the recursive end condition, if so, the current result is saved and returned;

  • In the current situation, go through all possible situations and try the next step;

  • When the recursion is complete, it immediately backtracks, and the way to backtrack is to cancel the previous attempt.

The code template

function fn(n) {

    // Step 1: Check whether the input or status is illegal.
    if (input/state is invalid) {
        return;
  }

    // Step 2: Should the recursion end?
    if (match condition) {
        return some value;
  }

    // Iterate over all possible scenarios
    for (all possible cases) {
  
        // Step 3: Try the possibility of the next step
        solution.push(case)
        / / recursion
        result = fn(m)

        // Step 4: Go back to the previous step
        solution.pop(case)}}Copy the code

题 39: Given an array of no duplicate elements and a target number, find all combinations of the candidates that can make the sum of the number and the number target. The numbers in the candidates can be selected repeatedly without limit.

Description:

  • All numbers (including target) are positive integers.

  • The solution set cannot contain repeated combinations.

Their thinking

They want all the non-repeating subsets, and the sum of the values of the elements in that subset is equal to a given target.

Idea 1: Violence.

List all combinations of subsets, and then determine one by one whether their sum is the given target value. The solution is very slow.

Idea 2: Backtracking.

  • Start with an empty collection and carefully add elements to it.

  • Each time you add, check that the current sum is equal to the given target.

  • If the sum has exceeded the target, there is no need to try the other elements, go back and try the other elements;

  • If the sum is equal to the target, we add the current combination to the result, indicating that we have found a combination that meets the requirement, and return, trying to find other sets.

Code implementation

int[][] combinationSum(int[] candidates, int target) {
    int[][] results;
    backtracking(candidates, target, 0, [], results - highlight in another color);return results;
}

void backtracking = (int[] candidates, int target, int start, int[] solution, int[][] results) => {
    if (target < 0) {
        return;
  }

    if (target === 0) {
        results.push(solution);
        return;
  }

    for (inti = start; i < candidates.length; i++) { solution.push(candidates[i]); backtracking(candidates, target - candidates[i], i, solution, results); solution.pop(); }}Copy the code

In the main function:

  • Define a Results array to hold the final result;

  • Call backtracking and pass in the initial case and results, where the initial case is to start with the first element and the initial subset is empty.

In the backtracking function:

  • Check whether the current sum of elements has exceeded the target value and subtract it from the target sum each time a new element is added.

  • If the sum exceeds the target value, go back and try something else.

  • If the sum is exactly equal to the target value, the current subset is added to the result.

In the circulating body:

  • Every time a new element is added, backtracking is immediately recursively called to see if the appropriate subset has been found

  • When we’re done recursing, it’s important that we delete the element that we tried last time from the subset.

That completes the backtracking.

Hint: this is one of the most classic backtracking topics, sparrow is small, but all the five organs. It completely reflects each stage of backtracking algorithm.

In LeetCode 51, place N queens on an N×N chess board, one in each row, so that they cannot attack each other. Given an integer N, return the number of different solutions for N queens.

Their thinking

The key to solve the N queen problem is how to judge whether the current placement of each queen is legal.

Use an array of columns[] to record the queen’s column in each row. For example, columns[0] = 6 if the queen of the first row is placed at the position of column 5. Place the queen from the first row, one per row. Assuming that there is no conflict, now place the queen on the col column of the first row and check if this makes sense.

The way to do this is to check for conflicts in both directions.

Code implementation

First, start at the first line and end at the front of the first row to see if the queen placed in that row is on the COL column, or on its diagonal, as follows.

boolean check(int row, int col, int[] columns) {
    for (int r = 0; r < row; r++) {
        if (columns[r] == col || row - r == Math.abs(columns[r] - col)) {
            return false; }}return true;
}
Copy the code

Then perform the backtracking operation as follows.

int count;

int totalNQueens(int n) {
    count = 0;
    backtracking(n, 0.new int[n]);
    return count;
}

void backtracking(int n, int row, int[] columns) {
    // Are queens placed in all n rows?
    if (row == n) {
        count++; // Find a new way to display
        return;
  }

    // Try to place the queen in each column of the current row
    for (int col = 0; col < n; col++) {
        columns[row] = col;
    
        // Check if it is valid, if it is, proceed to the next line
        if (check(row, col, columns)) {
            backtracking(n, row + 1, columns);
        }
    
        // Do not put queens in this column if it is illegal (backtrack)
        columns[row] = -1; }}Copy the code

Algorithm analysis of backtracking is actually achieved by recursion, so when we analyze the time complexity of backtracking, we are actually analyzing the recursive function, the method is the same as introduced before.

Example: Analyze the time complexity of queen N.

Assume that the backtracking function is executed at T(n).

Solution:

I have to go through all the columns every time, and there are n columns.

  • In each traversal, the check function should be used to check whether the current placement method will cause conflicts. The time complexity of the check is determined by the current row and the upper limit is N, so the total time complexity is O(n2).

  • Recursively we try to put each one, and when we put the first queen, we have n-1 queens left to deal with, and the size of the problem is reduced by one, so the execution time becomes T(n-1).

Finally, the expression of T(n) is obtained: T(n) = n×T(n-1) + O(n2).

T(n) is expanded by iterative method to obtain:

T of n is n times n minus 1 times T of n minus 2 plus n minus 1, 2 plus n2

…

T(n) = n×(n-1)×(n-2)×… 1 + 1 + 22 + 32 +… (n – 1)2 + n2

The first part is the factorial and the second part is the sum of squares. According to the formula, the final result is:

T(n) = n! + n(n+1)(2n+1)/6

O(T(n)) = n! + O(n3)

Due to the n! >n3, so the upper bound is n factorial. O(T(n)) = n!

conclusion

Recursion and backtracking are arguably one of the most important algorithms in algorithm interviewing, and many other algorithms have their shadow. For example, the definition and traversal of binary trees take advantage of recursion; We also use recursion for merge sort and quicksort; Dynamic programming is actually an optimization of recursion; There is binary search, which can also be implemented by recursion.

Note: to master the method of analyzing the complexity of recursion, one must have a solid mathematical foundation, such as the arithmetic sequence, geometric sequence, etc. summation formula to remember.

Advice: LeetCode does a good job of sorting recursive and backtracking questions, and has a rich question bank. I suggest you to do more.