Cocolib

Appearance

On this page

全排列 ​

Question

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

思路 ​

与组合的不同之处在于：

  • 不能每次从startIndex开始往下递归了，因为每一次搜索需要考虑之前已经被搜索的元素，只不过不考虑已经被放入path数组中的元素
  • 多了一项去重的操作，不能考虑已经被放入path数组中的元素

46.全排列

js
var permute = function(nums) {
    const res = []  // 结果[][]
    const path = [] // 每次递归的结果[]
    // used[] ：记录已经放入path[]中的元素
    const backtracking = (used)=>{
        if(path.length===nums.length){		// 终止条件
            res.push([...path])		// 存放结果
            return
        }
        for(let i= 0 ;i<nums.length;i++){	// 每次从 0 开始
            if(used[i]===1) continue
            path.push(nums[i])				// 处理节点 
            used[i]=1
            backtracking(used)		// 递归
            path.pop()					//回溯
            used[i]=0
        }
        
    }
    backtracking([])
    return res
};