[数据结构与算法]全排列（回溯）JavaScript

忘是亡心i 2022-12-12 13:57 175阅读 0赞

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:
    
    输入: [1,2,3]
    输出:
    [
      [1,2,3],
      [1,3,2],
      [2,1,3],
      [2,3,1],
      [3,1,2],
      [3,2,1]
    ]

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/permutations  
题解：

/** * @param {number[]} nums * @return {number[][]} */
        var permute = function (nums) { 
          const res = []
          const backtrack = (path) => { 
            if (path.length === nums.length) { 
              res.push(path)
              return
            }
            nums.forEach(n => { 
              if (path.includes(n)) { 
                return
              }
              backtrack(path.concat(n))
            })
          }
          backtrack([])
          return res
        }

时间复杂度：O（n！）每次递归嵌套一次循环，每次循环为n-递归层数，所以时间复杂度是n(n-1)(n-2)…(1)  
空间复杂度：递归堆栈O（n） 这个n是递归层数，这个题中层数就等于nums.length

当然也可以用`push和pop方法配合[...path]`代替`path.concat(n)`这种写法  
如果forEach要改写为for循环，  
在for循环语句中可以使用 break/continue  
使用 `continue` 代替forEach中的 `return` 或者 `return true`  
使用 `break`代替forEach中的 `return false`；

var permute = function (nums) { 
                const res = []
                const backtrack = (path) => { 
                    if (path.length === nums.length) { 
                        res.push([...path])
                        return
    
                    }
                    for (let i = 0; i < nums.length; i++) { 
                        if (path.includes(nums[i])) { 
                            continue
                        }
                        path.push(nums[i])
                        backtrack(path)
                        path.pop()
                    }
    
                }
                backtrack([])
                return res
            }
            console.log(permute([1, 2, 3]))