没有重复元素集合的全排列 2022-03-19 周六

题目

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

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums 中的所有整数 互不相同

• 示例 1：
  输入：nums = [1,2,3]
  输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

• 简单易懂 Java/ C++/Python/js/go - 全排列

思路

• 深度为nums.length；度为nums.length的完全树的深度优先遍历

• 回溯：要去掉path中最后一个元素？？？

• 剪枝：去重；

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    // 判空
    if (!nums) return [];

    // 结果数组；数组的数组
    const result = [];

    // 深度优先遍历的数组
    const path = [];

    // 深度为nums.length的完全树深度优先遍历
    const dfs = () => {
        // 递归的退出条件
        if (path.length === nums.length) {
            // 长度满足条件，推入res数组
            result.push(path.slice());
            return;
        }

        // 树的度为nums.length，所以要递归多次
        for (let i = 0; i < nums.length; i++) {
            // 剪枝：去重
            if (path.includes(nums[i])) {
                continue;
            }

            // 把当前元素加入path
            path.push(nums[i]);

            // 递归调用
            dfs();

            // 回溯；要去掉最后一个元素
            path.pop();
        }
    };
  
    // 开始执行深度优先遍历
    dfs();

    return result;
};