【Day 82 】2023-05-06 - 47 全排列 II

[azl397985856]

47 全排列 II

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/permutations-ii/

前置知识

• 回溯
• 数组
• 剪枝

  题目描述

  
  给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1]

[Zoeyzyzyzy]

class Solution {
    //存放结果
    List<List<Integer>> result = new ArrayList<>();
    //暂存结果
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        boolean[] used = new boolean[nums.length];
        Arrays.fill(used, false);
        Arrays.sort(nums);
        backTrack(nums, used);
        return result;
    }

    private void backTrack(int[] nums, boolean[] used) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            // used[i - 1] == true，说明同⼀树⽀nums[i - 1]使⽤过
            // used[i - 1] == false，说明同⼀树层nums[i - 1]使⽤过
            // 如果同⼀树层nums[i - 1]使⽤过则直接跳过
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            //如果同⼀树⽀nums[i]没使⽤过开始处理
            if (used[i] == false) {
                used[i] = true;//标记同⼀树⽀nums[i]使⽤过，防止同一树枝重复使用
                path.add(nums[i]);
                backTrack(nums, used);
                path.remove(path.size() - 1);//回溯，说明同⼀树层nums[i]使⽤过，防止下一树层重复
                used[i] = false;//回溯
            }
        }
    }
}

[LIMBO42]

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        ans = []
        vec = []
        nums.sort()
        n = len(nums)
        used = [False] * n
        def dfs(vec, used):
            if len(vec) == n:
                ans.append(vec[:])
                return
            for i in range(0, n):
                if i >= 1 and nums[i] == nums[i-1] and used[i-1] == False:
                    continue
                if used[i] == False:
                    used[i] = True
                    vec.append(nums[i])
                    dfs(vec, used)
                    used[i] = False
                    vec.pop()
        dfs(vec, used)
        return ans

[RestlessBreeze]

code

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;

    void backtrack(vector<int>& nums, vector<int>& used)
    {
        if (path.size() == nums.size())
        {
            res.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++)
        {
            if (i > 0 && used[i - 1] == 0 && nums[i] == nums[i - 1])
                continue;
            if (used[i] == 1)
                continue;
            used[i] = 1;
            path.push_back(nums[i]);
            backtrack(nums, used);
            path.pop_back();
            used[i] = 0;
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<int> used(nums.size(), 0);
        sort(nums.begin(), nums.end());
        backtrack(nums, used);
        return res;
    }
};

[Abby-xu]

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        ans = [[]]
        for n in nums:
            new_ans = []
            for l in ans:
                for i in range(len(l)+1):
                    new_ans.append(l[:i]+[n]+l[i:])
                    if i<len(l) and l[i]==n: break              #handles duplication
            ans = new_ans
        return ans

[csthaha]

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function(nums) {
    const res = [];
    const visited = new Array(nums.length).fill(false);
    const  backTrack = (path) => {
        if(path.length === nums.length) {
            res.push(path);
            return;
        }

        for(let i = 0; i < nums.length; i++) {
            if(visited[i] || (i > 0 && nums[i] === nums[i - 1] && !visited[i - 1])) continue;
            path.push(nums[i]);
            visited[i] = true;
            backTrack(path.concat());
            path.pop();
            visited[i] = false;
        }
    }
    nums.sort((x, y) => x - y);
    backTrack([])
    return res;
};

[bookyue]

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        return dfs(nums, new boolean[n], new ArrayDeque<>(n), new ArrayList<>(n * n));
    }

    private List<List<Integer>> dfs(int[] nums, boolean[] used, Deque<Integer> path, List<List<Integer>> ans) {
        if (path.size() == nums.length) {
            ans.add(new ArrayList<>(path));
            return ans;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]))
                continue;

            used[i] = true;
            path.addLast(nums[i]);
            dfs(nums, used, path, ans);
            path.removeLast();
            used[i] = false;
        }

        return ans;
    }

[kofzhang]

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = set()
        n = len(nums)
        nums.sort()
        def dfs(a ,li):
            if len(li )==n:
                res.add(tuple(li.copy()))
                return
            for i in range(len(a)):
                if i== 0:
                    li.append(a[0])
                    dfs(a[1:], li)
                    li.pop()
                if i > 0 and a[i] != a[i - 1]:
                    a[0], a[i] = a[i], a[0]
                    li.append(a[0])
                    dfs(a[1:], li)
                    li.pop()
                    a[0], a[i] = a[i], a[0]

        dfs(nums, [])
        return list(res)

[wangqianqian202301]

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        self.dfs(nums, [], res)
        return res

    def dfs(self, nums, path, res):
        if not nums:
            res.append(path)
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i-1]:
                    continue
            self.dfs(nums[:i]+nums[i+1:], path+[nums[i]], res)

[huizsh]

public List<List> permuteUnique(int[] nums) {

List<List<Integer>> res = new ArrayList<>();

if (nums == null || nums.length == 0)
    return res;

boolean[] visited = new boolean[nums.length];
Arrays.sort(nums);
dfs(nums, res, new ArrayList<Integer>(), visited);

return res;

}

public void dfs(int[] nums, List<List> res, List tmp, boolean[] visited) {

if (tmp.size() == nums.length) {

    res.add(new ArrayList(tmp));
    return;
}

for (int i = 0; i < nums.length; i++) {

    if (i > 0 && nums[i] == nums[i - 1] && visited[i - 1])
        continue;

    //backtracking
    if (!visited[i]) {

        visited[i] = true;
        tmp.add(nums[i]);
        dfs(nums, res, tmp, visited);
        visited[i] = false;
        tmp.remove(tmp.size() - 1);
    }
}

}

[snmyj]

class Solution {
public:
            vector<vector<int>> res;
             vector<int> path;
             vector<bool> sign;

    vector<vector<int>> permute(vector<int>& nums) {
             int size=nums.size();
             sign=vector<bool>(nums.size());
             dfs(nums,0);
             return res;

             }

    void  dfs(vector<int>& n,int m)
    {
        if(m==n.size()) {
            res.push_back(path);
            return;
        }
        for(int i=0;i<n.size();i++){
            if(!sign[i])
            {
            path.push_back(n[i]);
            sign[i]=true;
            dfs(n,m+1);
            sign[i]=false;
            path.pop_back();

        }
        }
    }
};

[JasonQiu]

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        used = [False] * len(nums)
        result = []

        def dfs(start, permutation, used):
            if start == len(nums):
                result.append(permutation[:])
                return
            for i in range(len(nums)):
                if not used[i]:
                    if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                        continue
                    used[i] = True
                    permutation.append(nums[i])
                    dfs(start + 1, permutation, used)
                    used[i] = False
                    permutation.pop()

        dfs(0, [], used)
        return result

[Diana21170648]

思路

回溯，考虑重复

class Solution:
     def backtrack(numbers, pre):
         nonlocal res
         if len(numbers) <= 1:
            res.append(pre + numbers)
            return#numbers列表的长度小于等于1,则将pre和numbers中的元素连接后添加到res列表中,然后返回
         for key, value in enumerate(numbers):
            if value not in numbers[:key]:
                backtrack(numbers[:key] + numbers[key + 1:], pre+[value])

     res = []
     if not len(nums):return []
     backtrack(nums, [])
     return res

**复杂度分析**

[harperz24]

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = []
        used = [False] * len(nums)
        nums.sort()
        self.backtrack(nums, 0, used, [], res)
        return res

    def backtrack(self, nums, start, used, perm, res):
        if start == len(nums):
            res.append(perm[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            # pruning
            if i > 0 and nums[i] == nums[i - 1] and used[i - 1]:
                continue

            perm.append(nums[i])
            used[i] = True
            self.backtrack(nums, start + 1, used, perm, res)
            perm.pop()
            used[i] = False

[FireHaoSky]

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        self.res = []
        check = [0 for i in range(len(nums))]

        self.backtrack([], nums, check)
        return self.res

    def backtrack(self, sol, nums, check):
        if len(sol) == len(nums):
            self.res.append(sol)
            return

        for i in range(len(nums)):
            if check[i] == 1:
                continue
            if i > 0 and nums[i] == nums[i-1] and check[i-1] == 0:
                continue
            check[i] = 1
            self.backtrack(sol+[nums[i]], nums, check)
            check[i] = 0

[joemonkeylee]

function permuteUnique(nums: number[]): number[][] { nums.sort((a, b) => b - a)

let res: Array<Array<number>> = []
let path: number[] = []
let used: boolean[] = [] 

backtrack(used)
return res

function backtrack(used: boolean[]): void {
    if (path.length === nums.length) {
        res.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
        }
    }
}

};

[tzuikuo]

思路

代码

class Solution {
public:
    vector<int> re;
    vector<vector<int>> results;
    set<vector<int>> results_s;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<int> used(nums.size());
        backtracing(nums,used);
        for(auto it=results_s.begin();it!=results_s.end();it++) results.push_back(*it);
        return results;
    }
    void backtracing(vector<int>& nums,vector<int>& used){
        if(ifallused(used)){
            //vector<int> re_s;
            //for(int ii=0;ii<re.size();ii++) re_s.push_back(re[ii]);
            //sort(re_s.begin(),re_s.end());
            results_s.insert(re);
            return;
        }
        for(int i=0;i<nums.size();i++){
            if(used[i]==0){
                re.push_back(nums[i]);
                used[i]=1;
                backtracing(nums,used);
                re.pop_back();
                used[i]=0;
            }
            else continue;
        }
    }
    bool ifallused(vector<int> &used){
        int flag=0;
        for(int i=0;i<used.size();i++){
            if(used[i]==0) flag=1;
        }
        return !flag;
    }
};

复杂度分析 -待定

[kangliqi1]

public List<List> permuteUnique(int[] nums) {

List<List<Integer>> res = new ArrayList<>();

if (nums == null || nums.length == 0)
    return res;

boolean[] visited = new boolean[nums.length];
Arrays.sort(nums);
dfs(nums, res, new ArrayList<Integer>(), visited);

return res;

}

public void dfs(int[] nums, List<List> res, List tmp, boolean[] visited) {

if (tmp.size() == nums.length) {

    res.add(new ArrayList(tmp));
    return;
}

for (int i = 0; i < nums.length; i++) {

    if (i > 0 && nums[i] == nums[i - 1] && visited[i - 1])
        continue;

    //backtracking
    if (!visited[i]) {

        visited[i] = true;
        tmp.add(nums[i]);
        dfs(nums, res, tmp, visited);
        visited[i] = false;
        tmp.remove(tmp.size() - 1);
    }
}

}

[Jetery]

class Solution {
public:
    vector<bool> st;
    vector<int> path;
    vector<vector<int>> ans;

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        st = vector<bool>(nums.size(), false);
        path = vector<int>(nums.size());
        dfs(nums, 0, 0);
        return ans;
    }

    void dfs(vector<int>& nums, int u, int start)
    {
        if (u == nums.size())
        {
            ans.push_back(path);
            return;
        }

        for (int i = start; i < nums.size(); i ++ )
            if (!st[i])
            {
                st[i] = true;
                path[i] = nums[u];
                if (u + 1 < nums.size() && nums[u + 1] != nums[u])
                    dfs(nums, u + 1, 0);
                else
                    dfs(nums, u + 1, i + 1);
                st[i] = false;
            }
    }
};

[lp1506947671]

class Solution:
    def backtrack(numbers, pre):
        nonlocal res
        if len(numbers) <= 1:
            res.append(pre + numbers)
            return
        for key, value in enumerate(numbers):
            if value not in numbers[:key]:
                backtrack(numbers[:key] + numbers[key + 1:], pre+[value])

    res = []
    if not len(nums): return []
    backtrack(nums, [])
    return res

复杂度分析

• 时间复杂度：由于由 visit 数组的控制使得每递归一次深度-1，因此递归的时间复杂度是N(N - 1) ... 1N∗(N−1)∗...∗1也就是O(N! op(res))O(N!∗op(res))，其中 N 是数组长度，op 操作即是昨天说的 res.add 算子的时间复杂度。

• 空间复杂度：O(N * N!)O(N∗N!)，考虑数组 N 个不重复元素，每一个排列占O(N)O(N)，共有 N!个排列。

[Lydia61]

全排列 2⃣️

class Solution {
public:
    vector<bool> st;
    vector<int> path;
    vector<vector<int>> ans;

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        st = vector<bool>(nums.size(), false);
        path = vector<int>(nums.size());
        dfs(nums, 0, 0);
        return ans;
    }

    void dfs(vector<int>& nums, int u, int start)
    {
        if (u == nums.size())
        {
            ans.push_back(path);
            return;
        }

        for (int i = start; i < nums.size(); i ++ )
            if (!st[i])
            {
                st[i] = true;
                path[i] = nums[u];
                if (u + 1 < nums.size() && nums[u + 1] != nums[u])
                    dfs(nums, u + 1, 0);
                else
                    dfs(nums, u + 1, i + 1);
                st[i] = false;
            }
    }
};

[chanceyliu]

代码

function permuteUnique(nums: number[]): number[][] {
  const ans: number[][] = [];
  const vis = new Array(nums.length).fill(false);
  const backtrack = (idx: number, perm: number[]) => {
    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;

};