preface

For some buckle problems, such as the full arrangement of this time, or the combination of problems mentioned before, backtrace method has a magic effect on them, with a resurrection, revitalization of the global role, can be said to be a necessary prescription for buckle journey! Let me introduce you to the panacea ———— “Backtrack”

Here’s a retrospective prescription:

Back in the template

Function backtracking {if (end condition) {backtracking; return; } for (select: elements in this layer's collection (the number of children of nodes in the tree is the size of the collection) {process nodes; Backtracking (path, select list); // undo the result of recursive backtracking}Copy the code

Next we’re going to “see a doctor.”

The title

Given an array nums that does not contain duplicate digits, return all possible permutations. You can return the answers in any order.

Example 1:

Output: input: nums = [1, 2, 3], [[1, 2, 3], [31] 1,,1,3 [2], [2,3,1], [3,1,2], [3, 2, 1]]Copy the code

Example 2:

Input: nums = [0,1] output: [[0,1],[1,0]Copy the code

Thought analysis

【1,2,3】 【1,2,3】

For example, track is used in our code to assist the stack that temporarily stores data. Let’s use the graph to see the logic of finding results by using the stack:

First stack display result

The display result of the second stack

The diagram above is only one subtree solution. There are two other subtrees that have similar paths. Let’s not draw them here.

explore

Before thinking about this kind of problem, you need to think clearly. This kind of backtracking problem is actually a “nested” process. We need to imagine what this arrangement would look like: a blueprint of our own ideas:

• The first thing is to push the 1, right? 2 in the stack? Or is it three? We need to talk about each of these three cases, so we’re going to push 1 in order;
• And then, if I push 2, if I push 3, then I’m going to push 2 for the moment,
• At the end of the stack, we’re done, because there are no numbers left.

This is the idea of depth-first traversal in backtracking. “Don’t hit the south wall and don’t look back”. One way is always to the end, and depth-first exploration and solution of binary tree will not stop until there is no way out or the target answer is found. At the end, we just push the result we found into the result array and return it.

The fallback

Some people said, we haven’t finished analyzing the first 1,2,3, how can we complete this? Hey, hey, take your time.

We have found one set of target outcomes in the above cases, but what about the others? At this point we need to understand another idea of backtracking: backtracking. It simply means going back to where we left off. In the case of the traceback problem, this step is very simple, track.pop(), yes you read that correctly, is the off stack operation. How does this work?

We found a set of results, for example, [1, 2, 3], then we perform fallback, until in [1] has been into the stack, but at this time of the 2, 3 choices, we started out as a choice 2 into the stack, so this time we changed our strategy, make 3 into the stack, so at this time and find a set of results, perform fallback again at this time, Until we start with 1,2, and 3, we just push 2 again, repeat the process, and finally get the result.

But how do you simulate this process? That’s the loop. And it’s important to note that this place is going to be de-duplicated.

Although the amount of backtracking code is small, but in fact you also know this process, space is relatively complex, is a typical space to exchange for time of an algorithm, but it still does not change its applicability, is still a necessary method for force buckle!

Specific code

var permute = function(nums) {
    const result = []
    backTrack(nums, result, [])
    return result
};

function backTrack (nums, result, track) {
    if (track.length === nums.length) {
        // Change the pointer to the reference type. Purpose; Prevents backtracking from affecting the current array state.
        result.push([...track])
        return
    }
    for (let i = 0; i < nums.length; i++) {
        if (track.includes(nums[i])) {
            continue
        }
        track.push(nums[i])
        backTrack(nums, result, track)
        track.pop()
    }
}
Copy the code

The code analysis

Here we need to define our result array result[], which is the space to hold the final result. The backTrack function is our core code, which uses the backTrack template, and if you compare it yourself, you can see that it’s really the same. There are some details that need to be paid attention to. For example, we used track.includes(nums[I]) to skip the selected numbers.

conclusion

In general, there is a method to brush questions, we need to summarize the method according to the questions made, not to say that brush questions more useful, brush questions only give you the experience of summarizing methods, rather than give us the power to brush more questions, the direction is wrong, so we still need to learn more, more summary.

I am small white, we pull together buckle!