This is the seventh day of my participation in the August More text Challenge. For details, see: August More Text Challenge

preface

About the LeetCode array type problem related solutions, it can be seen that LeetCode array type problem before doing must see, classification solution summarized the problem, can be used to improve a single. If you think it is helpful, remember to give more likes and attention, thank you!

Topic describes

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], [31] 1,,1,3 [2], [2,3,1], [3,1,2], [3, 2, 1]]

Example 2: input: nums = [0,1] output: [[0,1],[1,0]]

Example 3: Input: nums = [1] Output: [[1]]

Link: leetcode-cn.com/problems/pe…

Answer key

This question is a typical DFS + backtracking mode problem. There is a template for arranging DFS, and you can use it directly. So let’s just give you the code

/ * * *@param {number[]} nums
 * @return {number[][]}* /
var permute = function(nums) {
    const n = nums.length
    let used = new Array(n).fill(0)
    let ans = []
    
    const dfs = (nums, d, n, used, curr, ans) = > {
        if (d === n) {
            ans.push([...curr])
            return
        }
        
        for (let i = 0; i < n; ++i) {
            if (used[i]) continue
            used[i] = 1
            curr.push(nums[i])
            dfs(nums, d+1, n, used, curr, ans)
            // Restore the original
            used[i] = 0
            curr.pop()
        }
    }
    
    dfs(nums, 0, n, used, [], ans)
    return ans
};
Copy the code

The main part of the code is the DFS function, which has several important points.

One is the recursive termination condition: D === n, where d is the number of elements in the curr array and n is the number of elements in the NUMs array. When all nums elements are added to the curr array, it means that one of the permuted arrays has been found and is then pushed into the ANS array.

One is the used array: the used array is used to mark whether nums[I] has been used, with 1 indicating yes and 0 indicating no. Since we need to start at I = 0 each time (in order to find all combinations), the used array must exist.

The other point is that after a recursive DFS, we have to pop the previously added nums[I] out of the curr and set used[I] to 0 so that the recursion will not be affected. This step is called backtracking. So we go back to where we were before. For the array [1, 2, 3], the process of solving the array can be seen in the following figure, which is derived fromliweiwei1419

Time complexity: An array of length n has a total of N! And to find each of these combinations requires going through the array once, so the time complexity is O(n * n!).