This is the 26th day of my participation in the More Text Challenge. For more details, see more text Challenge

Full permutation (Question No. 46)

The title

Given an array nums with no duplicate digits, return all possible permutations of it. You can return the answers in any order.

Example 1:

Input: nums = [1.2.3] Output: [[1.2.3], [1.3.2], [2.1.3], [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

Tip:

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • numsAll integers inEach other is not the same

link

Leetcode-cn.com/problems/pe…

explain

This one, this one is a classic permutation.

Again, it’s an easy one, you just have to think about all the combinations, and it says there’s no repeating numbers, so it’s even easier.

The official recommendation is to do this recursively, each time you need to pay attention to the current array length, and the use of the number (used or not), and then continue to trace back, make sure to update the use of the number in the process of traceback, otherwise you will use the number repeatedly or not at all.

However, I do not recommend this method here, because it is relatively complex, and the time complexity should come to O(n2). Is there a simpler method?

This is the first method I thought of. Yes, I didn’t think of looking back, but simply listed all the possibilities.

For example, such a 🌰 :

[1.2.3]
Copy the code

First unassemble the array, which can be divided into three arrays like 👇 :

[1]
[1.2]
[1.2.3]
Copy the code

The first array is very simple. There is only one case, and that is:

[1]
Copy the code

What if I add another array? There should be two cases 👇 :

[1.2]
[2.1]
Copy the code

There’s actually a feature here, the number 2 is inserted before and after the number 1, which is 0 and 1 in terms of index.

What if I had another number?

So I can insert three positions, zero, one, two.

So it’s inserted at the head, middle, and tail of an array of length two, or in all of the gaps.

Is that the point of view? Yes, it’s that simple.

All you need to do is insert a new number into each of the existing arrays, and then record the new array until you run out of numbers, and then you have all the possibilities.

Your own answers (permutation and combination)

Without further ado, take a look at the code 👇 :

var permute = function(nums) {
  var res = [[nums[0]]]
  nums.shift()
  for (const num of nums) {
    var len = res.length - 1
    while (len >= 0) {
      var arr = res.shift()
      for (let i = 0; i <= arr.length; i++) {
        arr.splice(i, 0, num)
        res.push([...arr])
        arr.splice(i, 1)   
      }
      len--
    }
  }
  return res
};
Copy the code

The first is the initial assignment. Since nums has a length of at least 1, the first element in NUMs is inserted directly into res and the first element in NUMs is removed.

Start next cycle remaining nums, each encounter a new number, all insert it into the res in all of the array aperture, here is a little need to pay attention to, because the array is a complex object, every time is point to the same memory address, so every time after inserting the new Numbers to drop this number to wipe out, otherwise there will be a number of repeat.

And then you just return res, and that’s your final answer.

Ordinary solution (backtracking)

Backtracking was mentioned in the last problem, and I’m not going to repeat the definition of backtracking.

The main traceback logic is to remember the length of the current array and the state of all the numbers (used or not), and then you can call the traceback method repeatedly to complete the solution 👇 :

var permute1 = function(nums) {
  var res = []
      obj = {}
  function DFS(arr) {
    if (arr.length === nums.length) return res.push([...arr])
    for (const num of nums) {
      if (obj[num]) continue
      obj[num] = true
      DFS(arr.concat([num]))
      obj[num] = false
    }
  }
  DFS([])
  return res
};
Copy the code

In a traceback method, the first line is the termination condition of the traceback, that is, when the array length is the same as nums, it is proved that the traceback has reached the end of the answer, and it is pushed directly into the RES.

Note the same problem here, because the arrays are all pointing to the same memory address, so use destructuring to generate a new array and push it into the RES, otherwise the changes to the posterior ordinal will affect the previous elements.

After the condition is terminated, the loop begins, working in numeric order. If the current number has been used, the loop is skipped.

If not, it changes its state to used, and then adds the current number to the array for the next recursive step. Finally, don’t forget to reset the number state to unused, otherwise the number will be missing.

The performance of this method is really poor, about 30% to 40% in both time and space. However, if the permutation and combination method is used, both of them can reach 90%, which is enough to prove that the official solution is sometimes not optimal, and there is still room for improvement.




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)

Those who are interested can also check out my personal homepage 👇

Here is RZ