力扣算法JS LC [46. 全排列] LC [47. 全排列 II]

菜鸡刷算法的一天，每天分享两题算法，大家有这个想法的，可以给我个关注，然后一起坚持每天的算法之旅。希望我们共同进步，一起加油。 ​ LC 46. 全排列

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

示例 1：

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

示例 2：

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

示例 3：

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

解题思路：使用标记，标记使用过的数字，pop 出来后消除标记

代码：

var permute = function(nums) {
    const res = [], path = [];
    backstracking(nums, []);
    return res;
    function backstracking(n, used) {
        if(path.length === nums.length) {
            res.push(Array.from(path));
            return;
        }
        for(let i = 0; i < nums.length; i++) {
            if(used[i]) continue; //判断是否有标记
            path.push(n[i]);
            used[i] = true;
            backstracking(n, used);
            path.pop();
            used[i] = false;
        }
​
    }
};

 

 

LC 47. 全排列 II

给定一个可包含重复数字的序列 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]]

解题思路：跟上面全排列一样，但是多了一步去重。使用 set 表去重

代码：

var permuteUnique = function(nums) {
    const res = [], path = [];
    const set = new Set();
    backstracking([]);
    return res;
    function backstracking(used) {
        if(path.length === nums.length) {
            let str = path.toString();
            if(!set.has(str)) {
                set.add(str)
                res.push(Array.from(path));
                return;
            }
        }
        for(let i = 0; i < nums.length; i++) {
            if(used[i]) continue
            path.push(nums[i]);
            used[i] = true;
            backstracking(used);
            path.pop()
            used[i] = false;
        } 
    }
};

​