Topic describes

Given a sequence without repeating digits, return all possible permutations.

The sample

Example 1:

Input: [1, 2, 3] output: [[1, 2, 3], [31] 1,,1,3 [2], [2,3,1], [3,1,2], [3, 2, 1]]Copy the code

Subject analysis

Given an array, return all the arrays that can be arranged without repeating themselves.

Their thinking

So this is going to be different from the previous problem, where we have to backtrack.

So what is a backtracking algorithm? In fact, the backtracking algorithm is an exhaustive method, but the backtracking algorithm uses pruning function to cut some nodes that are impossible to reach the final state (i.e. the answer state), so as to reduce the generation of nodes in the state-space tree.

In that case, it may not be so specific, but look at this picture.

In this case, because we need to return an array that does not repeat itself, we need to do some pruning in the backtrace. If we encounter something different from ourselves, we will continue. If we encounter something identical, we will skip it. After each branch recurses, we need to go to another branch to recurse, so we need to undo the current selection, go back to the previous selection, go to the next branch and repeat the previous operation.

It’s kind of like a tree’s depth-first traversal, where you go to the end of one path, and if you find that you can’t get there, you go back to the upper branch, and if there are more branches that haven’t been walked, you start with the branches that haven’t been walked. The cycle repeats until each branch has been completed.

AC code

var permute = function(nums) { let res = [] let recursion = (path, Set) => {if(path.length == nums.length) {// If (path.length == nums.length) {// If (path.length == nums.length) {// If (path.length == nums.length) {// If (path.length == nums.length) { Return for(let I = 0; let I = 0; let I = 0; i < nums.length; I++) {// iterate over if(! Set.has (nums[I])) {// If path.push(nums[I]) does not exist in the set // push the element into the path set.add(nums[I]) // store the element in the set Set. Delete (nums[I]) // Set like path}}} Recursion ([],new Set()) return res};Copy the code

conclusion

There’s still a lot of practice with backtracking, and I believe that doing more backtracking problems will help you understand backtracking better. If there is something wrong or need to be modified in the article, please leave a comment in the comment section, so that I can find the problem in time, thank you XDM.

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign