“This is the 24th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

46. The whole arrangement

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

Answer key

Recursion + backtracking + prune

Recursively retrace all possible outcomes; You can refer to the following figure

Graph of TD 1 - > 1, 1, 1, 2 and 1, 1, 1 - > 1,1,1 &1,1,2 &1,1,3 1, 2 - > 1, 2, 1 &1,2,2 & 1, 2, 3, 1, 3 - > 1,3,1 & 31 & 1 filling 2 - > 2, 1 & 2, 2, 2, 3, 2, 1 - > 2,1,1 & 2,1,2 &,1,3 2, 2 - > 2, 2, 1 & 2,2,2 & 2, 2, 3, 2, 3 - > 2,3,1 & 31 & 2 filling 3 - > 3, 1 & 3, 3, 3, 1, 2 and 3 - > 3,1,1 & 3,1,2 & 3,1,3 3, 2 - > 3, 2, 1 & 3,2,2 & 3, 2, 3, 3, 3 - > 3,3,1 & 3 31 & 3 filling

Code implementation can first write a minimal version, code with comments, does it look very simple?

var permute = function(nums) {
    // Array length
  const len = nums.length;
  / / recursion
  dfs([]);
  function dfs(path) {
      // Recursive exit
    if (path.length === len)return
    for (let i = 0; i < len; i++) {
        // Count the elements on the path and put them into the path array
        path.push(nums[i]);
        dfs(path);
        / / backpath.pop(); }}};Copy the code

But watch nums = [1, 2, 3] nums = [1, 2, 3] nums = [1, 2, 3] recursive back reference,,1,1 [1], [1,1,2],1,1 [1], [1,1,2],1,1 [1], [1,1,2] this does not conform to the requirements of branching structure also came out, The requirement of our problem is that there are no duplicate numbers;

So elements on the statistical path need to be counted conditionally

Conditional statistics are pruned statistics that meet the conditions, and those that do not meet the conditions end recursion

What condition, no duplicate numbers is the condition, now the path array PathPathPath records all the elements that have been counted, as long as the new elements are not equal to the elements that pathPathPath already has

I’m going to write an isChecKischeccheck based on this idea; Look at the notes. It’s very simple

function isCheck(path, i) {
    // path The selected elements on the recursive path,
    // I wants to put I in path
    for (let j = 0; j < path.length; j++) {
        // No, this element has already been selected on the recursive path
      if (path[j] === i) return false;
    }
    // Yes, go ahead
    return true;
  }
Copy the code

Edit the code as follows

Time complexity: O(n∗n!) O(n * n!) O (n ∗ n!)

Complete code code

var permute = function(nums) {
  const len = nums.length;
  const result = [];
  dfs([]);
  return result;
  function dfs(path) {
    if (path.length === len) {
      result.push([...path]);
      return;
    }

    for (let i = 0; i < len; i++) {
      if(isCheck(path, nums[i])) { path.push(nums[i]); dfs(path); path.pop(); }}}function isCheck(path, i) {
    for (let j = 0; j < path.length; j++) {
      if (path[j] === i) return false;
    }
    return true; }};Copy the code

conclusion

Recursion + backtracking + pruning is a classical algorithm. The author has just started to learn, please understand the deficiencies, if you have comments and suggestions welcome to discuss in the comment section