The title

LeetCode 46 all permutations

Analysis of the

There are two main characteristics of backtracking algorithm: one is to traverse all situations; The other is that once you find a solution that works, you go back to the previous step and iterate over the other cases.

The first feasible solution we traversed in the problem is:

1 -> 2 -> 3      // If the feasible solution condition is satisfied, go back to the second place and continue to iterate over the other cases of the second place
1 -> 3           // The second traversal reaches 3. If the condition is not satisfied, the second traversal continues
1 -> 3 -> 2      // The third bit is traversed to 2, and the rollback begins
2                // The first is traversed to 2, and so on
2 -> 1
2 -> 1 -> 3. Until I've gone through all the casesCopy the code

implementation

/ * * *@param {number[]} nums
 * @return {number[][]}* /
const permute = function(nums) {
  const res = [];
  let tmp = [];
  const backTrack = (nums) = > {
    // Recursive exit condition
    if(tmp.length == nums.length) {
      res.push([...tmp]);
      return;
    }
    
    for(let num of nums) {
      // Find a non-repeating solution and add it to the intermediate variable
      if(tmp.indexOf(num) < 0) {
        tmp.push(num);
        backTrack(nums);
        tmp.pop(num);
      }
    }
  }
  
  backTrack(nums);
  
  return res;
};
Copy the code

conclusion

Backtracking algorithm focuses on “backtracking”. There is a back and forth, and after going through a situation, you need to go back to the previous step. Here’s the key to understanding the backtracking algorithm. In code, the previous step of the traceback adds the child to the array, and the next step removes the child. It’s a little convoluted at first, but if you draw the call stack, it’s easy to understand. The process of removal is actually called after a viable solution is completed, not immediately removed.

“A front-end learning small transparent, hard to learn front-end knowledge, at the same time to share their own thoughts on life, welcome to discuss and exchange. If my article is helpful to you, please click a like, will be very grateful for your encouragement.”

Backtracking algorithm problem of permutations opportunely | creator training camp The campaign is under way…