This is the fifth day of my participation in Gwen Challenge

Application of recursion and backtracking

See recursion from the full permutation

In our previous study, in fact, we all know that it is an exhaustive enumeration of all permutations. In a more popular way, if there are three numbers, we can see what number we have in each pit at a time, because each pit puts a number until the last pit gets a permutation. Which we found that involves a things, is what we do in every hole position is the same, we also know that exhaustive, we will use recursion, so now that involve the recursion, we need a border, we assume that each hole has a subscript, so a total of the pit of digit is n, the subscript starting from 0, The subscript of the last pit is n-1, and by the time we find the NTH pit, it will be the boundary. Because we can’t find any pit with subscript n, let’s implement this code:

 function permute(nums) {
    // Define the length of the array
    const len = nums.length
    // Define an array to record the contents of the current arrangement
    const curr = []
    // Define an object to hold the used array
    const visited = {}
    // Define an array to hold existing permutations
    const res = []
    // Define the DFS function, the entry is the pit index (counting from 0)
    function dfs(num) {
        // This is the boundary
        if(num === len) {
            // The first len pits have been filled
            res.push(curr.slice())
            return
        }
        // Check the remaining numbers in your hand
        for(let i = 0; i < len; i++) {
            // If this number is not used in the previous pit
            if(! visited(nums[i])) {// Make a mark
                visited[nums[i]] = 1
                // Put the current number into curr
                curr.push(nums[i])
                // Proceed to the next pit based on this arrangement
                // The next pit is based on the previous pit,
                // So it is necessary to preserve the state of the number of pits,
                // The end of the recursion is to get an array
                dfs(num+1)
                // You have already completed the previous iteration
                // So we need to remove the used token state of the current number and exclude the number from the current array
                // nums[I] drop the current pit
                curr.pop()
                // Drop the "used" flag
                visited[nums[i]] = 0}}}// Start from the pit with index 0
    dfs(0)
    return res
}
Copy the code

Two points to note here:

• Why label with Map structure? This is because when we do not use a number, we can avoid the repeated use of the number that has been used. When this number leaves this pit, we need to cancel its Visited state

• The second point is why we use push(cur.slice ()) instead of push(curr) when we reach the recursive boundary, because curr is a global variable whose value is updated as the DFS function executes. So the purpose of the slice method is to make a copy that doesn’t affect curr, in case we modify the reference directly to curr

Combination problem: Changing “pit position”, unchanged “routine”

Bo:

Given an array of integers with no repeating elements, return all possible subsets (power sets) of nums. Note: The solution set cannot contain duplicate subsets.

Example: the input: nums = [1, 2, 3] output: [[3], [1], [2], [1, 2, 3], [1, 3], [2, 3], [1, 2], []]

Topic actually is easy to understand, also with us on the topic is about, is also a type of DFS, involves the DFS, not little thought of recursion, these knowledge tree, on a topic put what number is each pit, the problem is each pit won’t put a number, so the general idea is the same, we look at the code directly:

function subsets(arr) {
    // Define a result array
    const res = []
    // Define a boundary
    const len = arr.length
    // Define a variable to hold the combination
    let subset = []
    // Define a recursive function
    function dfs(index) {
        // Each time you enter this function, you have a new arrangement, so put the copy into the result array
        res.push(subset.slice())
        // Start the index from the current index
        for(let i = index; i< len; i++) {
            // Put the current number into the array
            subset.push(arr[i])
            // Start recursion on the next index
            dfs(i+1)
            // This step indicates that the previous situation has been completed, so release this number
            subset.pop()
        }

    }

    // Start with index 0
    dfs(0)

    // Return the result
    return res
}

console.log(subsets([1.2.3.4.5]))
Copy the code

After the above thought we found that, in fact, the main problem is how to recurse, so we need to think clearly, this problem is the main need to recurse where, this step to think clearly, we can start.

What do you mean backtrack

The word “day”, high-end, backdating, is that the time backdating? I’m going back three seconds, and I’m the Time assassin! Sorry, wrong set! In fact, we have experienced a backtracking, backtracking is a priority algorithm, namely we tried to search a selection condition, but when we can’t get what we want, we again take a step back to take another road, is not familiar, we have described in the previous section DFS the depth first search, So we can regard backtracking as a step of DFS backtracking. In fact, the two are basically the same thing.

conclusion

In fact, recursion and backtracking go hand in hand, and wherever there is recursion there is backtracking, so we tend to combine the two to understand learning, so did you fail?