数据结构与算法之递归: LeetCode 47. 全排列 II (Ts版)

全排列 II

• https://leetcode.cn/problems/permutations-ii/description/

描述

• 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列

示例 1

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2

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

提示

• 1 <= nums.length <= 8
• -10 <= nums[i] <= 10

Typescript 版算法实现

1 ) 方案1：搜索回溯

function permuteUnique(nums: number[]): number[][] {
    // 数字有重复，排列不能重复
    nums.sort((a, b) => b - a)
    let ret = []
    let path = []
    const backtrack = (used) => {
        if (path.length === nums.length) {
            ret.push([...path])
            return
        }
        for (let i = 0; i < nums.length; i++) {
            let num = nums[i]
            if (nums[i] === nums[i - 1] && !used[i - 1]) {
                continue
            }
            if (!used[i]) {
                used[i] = true
                path.push(num)
                backtrack(used)
                path.pop()
                used[i] = false
            }

        }
    }
    backtrack([])
    return ret
};

2 ) 方案2：搜索回溯-优化版

function permuteUnique(nums: number[]): number[][] {
    const ans = [];
    const vis = new Array(nums.length).fill(false);
    const backtrack = (idx, perm) => {
        if (idx === nums.length) {
            ans.push(perm.slice());
            return;
        }
        for (let i = 0; i < nums.length; ++i) {
            if (vis[i] || (i > 0 && nums[i] === nums[i - 1] && !vis[i - 1])) {
                continue;
            }
            perm.push(nums[i]);
            vis[i] = true;
            backtrack(idx + 1, perm);
            vis[i] = false;
            perm.pop();
        }
    }
    nums.sort((x, y) => x - y);
    backtrack(0, []);
    return ans;
};

原文地址：https://blog.csdn.net/Tyro_java/article/details/145233874

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！