Sincerely ask you to pay attention to and praise, original is not easy, your support is the biggest power of my writing!

Topic describes

Give you an array nums, nums of different numbers, return nums 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

Example 3:

Input: nums = [1] Output: [[1]Copy the code

Thought analysis

This is also a topic to investigate the backtracking algorithm. With reference to the previous problem-solving ideas, the analysis is as follows:

The arguments to the traceback function are generally a collection of arrays to be selected and a selected value. This problem just needs the array to be selected and the selected values

Initialization:

  • The optional array is nums
  • The selected one is clearly empty

Backtracking algorithm body: iterate over the selection array, pick a value in the currently selected array, the new selection array is the array with the current value removed, the new selection array and the new selected value into the next recursion

Recursive exit: When the length of the array to be selected is 1, that is, there is only one element left, add this value to the selected array, push the result into the result array and return it.

AC code

This is the first serious backtracking algorithm I have written. Due to my lack of familiarity with backtracking and lack of understanding, a lot of codes are written by constant trial and grope. Please forgive me if the code is a little ugly.

var permute = function (nums1) {
  const result = [];
  const recursion = (nums, acc) = > {
    if (nums.length === 1) {
      result.push(nums.concat(acc));
    } else {
      for (let i = 0; i < nums.length; i++) {
        let current = [];
        if(nums.length ! == nums1.length) { current = [...acc]; } current.push(nums[i]);let rest = [];
        // Generate rest to recurse
        if (i === 0) {
          rest = nums.slice(1);
        } else if (i === nums.length - 1) {
          rest = nums.slice(0, nums.length - 1);
        } else {
          rest = [...nums.slice(0, i), ... nums.slice(i +1)]; } recursion(rest, current); }}}; recursion(nums1, []); };Copy the code

conclusion

For the understanding of recursion, I suggest you do the binary tree first, brush a few questions after you will have a new understanding of recursion, and can be more skilled in practice, know how the program will recurse, how to return the function. Recursion is the foundation of programming, many algorithms are inseparable from recursion, such as backtracking, such as the idea of dynamic planning, such as divide and conquer, on the basis of mastering recursion to learn these algorithms will get twice the result with half the effort!

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