azl397985856 commented 2 years ago

47 全排列 II

入选理由

暂无

题目地址

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

前置知识

回溯
数组

剪枝

题目描述


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

示例:

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

xinhaoyi commented 2 years ago

class Solution{ public List<List> permuteUnique(int[] nums){ // 首先是特判 int len = nums.length; // 使用一个动态数组来保存所有可能的全排列 List<List> res = new ArrayList<>(); if(len == 0){ return res; }

    // 对数组进行排序，方便下面preNum判断之前的数
    Arrays.sort(nums);

    // 一个布尔数组 used，初始化的时候都为 false 表示这些数还没有被选择，
    // 当我们选定一个数的时候，就将这个数组的相应位置设置为 true ，
    // 这样在考虑下一个位置的时候，就能够以 O(1） 的时间复杂度判断这个数是否被选择过，
    // 这是一种“以空间换时间”的思想。
    boolean[] used = new boolean[len];

    // path 这个变量所指向的对象在递归的过程中只有一份，
    // 深度优先遍历完成以后，因为回到了根结点（因为我们之前说了，从深层结点回到浅层结点的时候，需要撤销之前的选择），
    // 因此 path 这个变量回到根结点以后都为空。
    List<Integer> path = new ArrayList<>();

    dfs(nums,len,0,path,used,res);
    return res;
}

private void dfs(int[] nums, int len, int depth, List<Integer> path, boolean[] used, List<List<Integer>> res) {
    // depth 用来记录递归到了第几层
    // 用来结束递归，拿到当前的结果之后再撤销回上一层
    if (depth == len){
    // res.add(path);
        res.add(new ArrayList<>(path));
        return;
    }

    // else进行递归
    // 遍历所有nums中的数字
    int preNum = nums[0] - 1; // 初始化preNum
    for (int i = 0; i < len; i++) {
        // 是否这个数字之前已经用过并且有没有重复
        if (!used[i] && (nums[i]!=preNum)){
            preNum = nums[i];
            path.add(nums[i]);
            used[i] = true;

            // 不断往下一层走
            dfs(nums, len, depth + 1, path, used, res);

            used[i] = false;
            path.remove(path.size() - 1);
        }
    }
}

}

yijing-wu commented 2 years ago

// time：O(n×n!)，其中 n 为序列的长度。每个backtracking 的部分最坏情况下没有重复数字共 n! 个，一共有n个数字，所以n×n! // space: 空间复杂度：O(n)。O(n)标记visited，递归栈深度O(n)，总O(n+n)=O(2n)=O(n)。

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];
        dfs(nums, path, visited, ans);
        return ans;
    }

    private void dfs(int[] nums, List<Integer> path, boolean[] visited, List<List<Integer>> ans) {
        if(path.size() == nums.length) {
            ans.add(new ArrayList<>(path));
        }
        for(int i = 0; i < nums.length; i++) {
            // remove duplicate
            if(i > 0 && visited[i-1] && nums[i] == nums[i-1]) {
                continue;
            }
            //
            if(!visited[i]) {
                path.add(nums[i]);
                visited[i] = true;
                dfs(nums, path, visited, ans);
                path.remove(path.size() - 1);
                visited[i] = false;
            }
        }
    }
}

zwx0641 commented 2 years ago

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

    void permutation(vector<int>& perm, vector<int>& nums, vector<bool>& visited) {
        if (perm.size() == nums.size()) {
            res.push_back(perm);
            return;
        }

        int pre = nums[0] - 1;
        for (int i = 0; i < nums.size(); i++) {
            if (!visited[i] && pre != nums[i]) {
                pre = nums[i];
                perm.push_back(nums[i]);
                visited[i] = true;
                permutation(perm, nums, visited);
                visited[i] = false;
                perm.pop_back();
            }
        }
        return;
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<int> perm;
        vector<bool> visited(nums.size());
        sort(nums.begin(), nums.end());
        permutation(perm, nums, visited);
        return res;
    }
};

QinhaoChang commented 2 years ago

思路： dfs + 剪枝

class Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]: nums.sort() res = [] temp = [] visited = [False for _ in range(len(nums))]

    self.dfs(nums, res, temp, visited)
    return res

def dfs(self, nums, res, temp, visited):
    if len(temp) == len(nums):
        res.append(temp[:])
        return 
    if len(temp) > len(nums):
        return 

    for i in range(len(nums)):
        if i > 0 and nums[i] == nums[i - 1] and not visited[i - 1]:
            continue
        if visited[i]:
            continue
        temp.append(nums[i])
        visited[i] = True
        self.dfs(nums,res,temp, visited)
        temp.pop()
        visited[i] = False

zjsuper commented 2 years ago

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

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

moirobinzhang commented 2 years ago

Code:

public class Solution { public IList<IList> PermuteUnique(int[] nums) { IList<IList> res = new List<IList>(); IList permutation = new List(); bool[] isVisited = new bool[nums.Length];

    Array.Sort(nums);
    DFSHelper(nums, isVisited, permutation, res);            

    return res; 
}

public void DFSHelper(int[]  nums, bool[] isVisited, IList<int> permutation, IList<IList<int>> res)
{
    if (permutation.Count == nums.Length)
    {
        if (!res.Contains(new List<int>(permutation)))
            res.Add(new List<int>(permutation));
        return;
    }

    for (int i = 0; i < nums.Length; i++)
    {
        if (isVisited[i])
            continue;

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

        isVisited[i] = true;
        permutation.Add(nums[i]);
        DFSHelper(nums, isVisited, permutation, res);             
        permutation.RemoveAt(permutation.Count - 1);
        isVisited[i] = false;            
    }

}

}

Alexno1no2 commented 2 years ago

# 剪枝条件1： 结果的长度==列表的长度，是一个有效结果
# 剪枝条件2： 当前元素和前一个元素值相同并且前一个元素还没有被使用过的时候，需要剪枝
# 答案： 全部遍历，修改 check 之后回溯内部累加，更新 temp_sol

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, temp_sol, nums, check):
        if len(temp_sol) == len(nums):
            self.res.append(temp_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(temp_sol+[nums[i]], nums, check)
            check[i] = 0

Tesla-1i commented 2 years ago

class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res = []
temp = []
visited = [False for _ in range(len(nums))]

    self.dfs(nums, res, temp, visited)
    return res

def dfs(self, nums, res, temp, visited):
    if len(temp) == len(nums):
        res.append(temp[:])
        return 
    if len(temp) > len(nums):
        return 

    for i in range(len(nums)):
        if i > 0 and nums[i] == nums[i - 1] and not visited[i - 1]:
            continue
        if visited[i]:
            continue
        temp.append(nums[i])
        visited[i] = True
        self.dfs(nums,res,temp, visited)
        temp.pop()
        visited[i] = False

yan0327 commented 2 years ago

func permuteUnique(nums []int) [][]int {
    sort.Ints(nums)
    n := len(nums)
    out := [][]int{}
    hash := make([]bool,n)
    var dfs func(temp []int)
    dfs = func(temp []int){
        if len(temp) == n{
            out =append(out,append([]int{},temp...))
            return
        }
        for i:=0;i<n;i++{
            if i>0&&nums[i]==nums[i-1]&&!hash[i-1]{
                continue
            }
            if hash[i]{
                continue
            }
            temp = append(temp,nums[i])
            hash[i] = true
            dfs(temp)
            hash[i] = false
            temp = temp[:len(temp)-1]
        }
    }
    dfs([]int{})
    return out
}

biaohuazhou commented 2 years ago

思路

回溯

代码

class Solution {
    boolean[] vis;

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> perm = new ArrayList<Integer>();
        vis = new boolean[nums.length];
        Arrays.sort(nums);
        backtrack(nums, ans, 0, perm);
        return ans;
    }

    public void backtrack(int[] nums, List<List<Integer>> ans, int idx, List<Integer> perm) {
        if (idx == nums.length) {
            ans.add(new ArrayList<Integer>(perm));
            return;
        }
        for (int i = 0; i < nums.length; ++i) {
            if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
                continue;
            }
            perm.add(nums[i]);
            vis[i] = true;
            backtrack(nums, ans, idx + 1, perm);
            vis[i] = false;
            perm.remove(idx);
        }
    }
}

复杂度分析 时间复杂度： O(n×n!)) 空间复杂度：O(n)

xuhzyy commented 2 years ago

class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        res = []

        def backtrack(start, path, used):
            if len(path) == len(nums):
                res.append(path[:])
                return

            for i in range(start, len(nums)):
                if used[i] or (i > 0 and nums[i] == nums[i-1] and used[i-1] == False):
                    continue
                path.append(nums[i])
                used[i] = True
                backtrack(0, path, used)
                used[i] = False
                path.pop()

        used = [False] * len(nums)
        backtrack(0, [], used)
        return res

junbuer commented 2 years ago

思路

回溯法

代码

class Solution(object):
def permuteUnique(self, nums):
    """
    :type nums: List[int]
    :rtype: 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

1149004121 commented 2 years ago

全排列 II

思路

为了避免排列组合元素相同但顺序不同的情况，需要对nums进行排序。为了避免出现1（0）,1（1）,2（2）和1（1）,1（0）,2（2）的情况，要避免第一个1不用而直接用第二个1的情况。

代码

var permuteUnique = function (nums) {
    let res = [];
    nums.sort((a, b) => a - b);
    const n = nums.length;
    dfs([], 0);
    return res;

    function dfs(prev, pos) {
    if (pos === (2 ** n - 1)) {
        res.push(prev.slice());
        return;
    };
    for (let i = 0; i < n; i++) {
        if ((pos & (1 << i)) === 0) {
        if (i > 0 && nums[i] === nums[i - 1] && ((pos & (1 << (i - 1))) === 0)) continue;
        prev.push(nums[i]);
        dfs(prev, pos | (1 << i));
        prev.pop();
        }
    }
    }
};

复杂度分析

时间复杂度：O(N*2^N) 。
空间复杂度：O(N) 。

ZacheryCao commented 2 years ago

Idea

Backtracking

Code

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        ans = []
        def backtracking(candidates, cur):
            if len(cur) == len(nums):
                ans.append(list(cur))
                return
            for i in candidates:
                if candidates[i] > 0:
                    cur.append(i)
                    candidates[i] -= 1
                    backtracking(candidates, cur)
                    cur.pop()
                    candidates[i] += 1
        backtracking( Counter(nums), [])
        return ans

Complexity:

Time: O(N * N!) Space: o(N)

rzhao010 commented 2 years ago

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) return res;

        Arrays.sort(nums);
        boolean[] used = new boolean[len];

        Deque<Integer> path = new ArrayDeque<>(len);
        dfs(nums, len, 0, used, path, res);
        return res;
    }

    private void dfs(int[] nums, int len, int depth, boolean[] used, Deque<Integer> path, List<List<Integer>> res) {
        if (depth == len) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < len; i++) {
            if (used[i]) {
                continue;
            }
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }
            path.addLast(nums[i]);
            used[i] = true;
            dfs(nums, len, depth + 1, used, path, res);
            used[i] = false;
            path.removeLast();
        }
    }
}

cszys888 commented 2 years ago

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

time complexity: O(n*n!) space complexity: O(n)

tongxw commented 2 years ago

思路

回溯 + 剪枝

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        boolean[] selected = new boolean[nums.length];
        Arrays.sort(nums);
        dfs(nums, selected, ans, path);
        return ans;
    }

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

        for (int i=0; i<nums.length; i++) {
            if (selected[i]) {
                continue;
            }
            if (i > 0 && !selected[i-1] && nums[i] == nums[i-1]) {
                //System.out.println("cut: i->" + i + " num: " + nums[i]);
                continue;
            }
            selected[i] = true;
            path.add(nums[i]);
            dfs(nums, selected, ans, path);
            path.remove(path.size() - 1);
            selected[i] = false;
        }
    }
}

TC: O(P(N, K)) SC: O(N)

LannyX commented 2 years ago

思路

backtrack

代码


class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        boolean[] visited = new boolean[nums.length];
        backtrack(nums, new ArrayList<>(), visited);
        return ans;
    }
    void backtrack(int[] nums, ArrayList<Integer> list, boolean[] visited){
        if(list.size() == nums.length){
            ans.add(new ArrayList<Integer>(list));
            return;
        }

        for(int i = 0; i < nums.length; i++){
            if(i > 0 && nums[i - 1] == nums[i] && visited[i - 1]){
                continue;
            }
            if(!visited[i]){
                list.add(nums[i]);
                visited[i] = true;
                backtrack(nums, list, visited);
                visited[i] = false;
                list.remove(list.size() - 1);
            }
        }
    }
}

haixiaolu commented 2 years ago

思路

回溯用hashmap记录每个数字出现的次数, 来避免重复

代码

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = []
        perm = []
        # hashmap
        count = { n: 0 for n in nums}
        for n in nums:
            count[n] += 1

        def dfs():
            if len(perm) == len(nums):
                res.append(perm.copy())
                return 

            for n in count:
                if count[n] > 0:
                    perm.append(n)
                    count[n] -= 1

                    dfs()
                    count[n] += 1
                    perm.pop()
        dfs()
        return res

复杂度分析

时间： O(n * n!)
空间： O(n)

herbertpan commented 2 years ago

思考

每一层recursion思考应该在Ith-index上放什么element

code

class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> ans = new ArrayList<>();
    boolean[] visited = new boolean[nums.length];
    helper(nums, 0, new ArrayList<>(), visited, ans);

    return ans;
}

private void helper(int[] nums, int start, List<Integer> curr, boolean[] visited, List<List<Integer>> ans) {
    if (start == nums.length) {
        ans.add(new ArrayList<>(curr));
        return;
    }

    for (int i = 0; i < nums.length; i++) {
        // this element has been used in previous levels
        // this element has been used in current level
        if (visited[i]) {
            continue;
        }

        // this element value has been used
        if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {
            continue;
        }

        visited[i] = true;

        curr.add(nums[i]);

        helper(nums, start + 1, curr, visited, ans);

        curr.remove(curr.size() - 1);

        visited[i] = false;
    }
}
}

complexity

time: O(n * n!)
space: O(n)

zhiyuanpeng commented 2 years ago

class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res = []
temp = []
visited = [False for _ in range(len(nums))]

    self.dfs(nums, res, temp, visited)
    return res

def dfs(self, nums, res, temp, visited):
    if len(temp) == len(nums):
        res.append(temp[:])
        return 
    if len(temp) > len(nums):
        return 

    for i in range(len(nums)):
        if i > 0 and nums[i] == nums[i - 1] and not visited[i - 1]:
            continue
        if visited[i]:
            continue
        temp.append(nums[i])
        visited[i] = True
        self.dfs(nums,res,temp, visited)
        temp.pop()
        visited[i] = False

xjhcassy commented 2 years ago

public List<List<Integer>> 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<Integer>> res, List<Integer> 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);
        }
    }
}

ivangin commented 2 years ago

code:

private void helper2(List<List<Integer>> res, int[] nums, int start) {
        if (start == nums.length) {
            List<Integer> list = new ArrayList<>();
            for (int num : nums) {
                list.add(num);
            }
            res.add(new ArrayList<>(list));
            return;
        }

        for (int i = start; i < nums.length; i++) {
            if (isUsed(nums, start, i)) {
                continue;
            }
            swap(nums, start, i);
            helper2(res, nums, start + 1);
            swap(nums, start, i);
        }
    }

    private void swap(int[] nums, int l, int r) {
        int temp = nums[l];
        nums[l] = nums[r];
        nums[r] = temp;
    }

    private boolean isUsed(int[] nums, int i , int j) {
        for (int x = i; x < j; x++) {
            if (nums[x] == nums[j]) {
                return true;
            }
        }

        return false;
    }

Richard-LYF commented 2 years ago

class Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]:

res用来存放结果

    if not nums: 
        return []
    res = []
    used = [0] * len(nums)
    def backtracking(nums, used, path):
        # 终止条件
        if len(path) == len(nums):
            res.append(path.copy())
            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] = 1
                path.append(nums[i])
                backtracking(nums, used, path)
                path.pop()
                used[i] = 0
    # 记得给nums排序
    backtracking(sorted(nums),used,[])
    return res

Aobasyp commented 2 years ago

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

空间复杂度：O(N * N!)

callmeerika commented 2 years ago

思路

回溯

代码

var permuteUnique = function(nums) {
    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;
};

复杂度

时间复杂度：O(n*n!)
空间复杂度：O(n)

googidaddy commented 2 years ago

var permuteUnique = function (nums) { let res = []; nums.sort((a, b) => a - b); const n = nums.length; dfs([], 0); return res;

function dfs(prev, pos) {
if (pos === (2 ** n - 1)) {
    res.push(prev.slice());
    return;
};
for (let i = 0; i < n; i++) {
    if ((pos & (1 << i)) === 0) {
    if (i > 0 && nums[i] === nums[i - 1] && ((pos & (1 << (i - 1))) === 0)) continue;
    prev.push(nums[i]);
    dfs(prev, pos | (1 << i));
    prev.pop();
    }
}
}

};

liuajingliu commented 2 years ago

代码实现

var permuteUnique = function(nums) {
    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;
};

复杂度分析

时间复杂度：$O(n×n!)$，其中 nn 为序列的长度
空间复杂度：$O(n)

declan92 commented 2 years ago

思路

1. 数组元素不能重复选,使用set或者状压变量保存已选元素;
2. 结果长度等于数组长度时,返回;
3. 排序树组,值相同元素相邻,跳过相同的相邻元素;或者直接使用set保存结果集去重;

java

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        backtrack(res, nums, new ArrayList<Integer>(), 0);
        return new ArrayList<>(res);
    }

    public void backtrack(List<List<Integer>> res, int[] nums, List<Integer> list, int state) {
        if (list.size() == nums.length) {
            res.add(new ArrayList<>(list));
            return;
        }
        int val = 11;
        for (int i = 0; i < nums.length; i++) {
            if ((state & 1 << i) != 0|| nums[i] == val) {
                continue;
            }
            list.add(nums[i]);
            backtrack(res, nums, list, state | 1 << i);
            val = list.get(list.size() - 1);
            list.remove(list.size() - 1);
        }
    }
}

时间:$O(n^n)$,n为数组长度空间:$O(n)$

shamworld commented 2 years ago

var permuteUnique = function(nums) {
    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;
};

guangsizhongbin commented 2 years ago

func permuteUnique(nums []int) (ans [][]int) { sort.Ints(nums) n := len(nums) // 当前排列的数组 perm := []int{} // 标记，已经用过的元素 vis := make([]bool, n) var backtrack func(int)

// idx 当前遍历的位置
backtrack = func(idx int) {
    // 到达目标
    if idx == n {
        ans = append(ans, append([]int(nil), perm...))
        return
    }

    for i, v := range nums {
        if vis[i] || (i > 0 && !vis[i-1] && v == nums[i-1]){
            continue
        }

        perm = append(perm, v)

        // 标记
        vis[i] = true
        backtrack(idx + 1)
        vis[i] = false
        perm = perm[:len(perm) - 1]
    }
}

// 从0的位置开始
backtrack(0)
return

}

Hacker90 commented 2 years ago

pwqgithub-cqu commented 2 years ago

class Solution { public List<List> permuteUnique(int[] nums) { List<List> ans = new ArrayList<>(); List path = new ArrayList<>(); boolean[] selected = new boolean[nums.length]; Arrays.sort(nums); dfs(nums, selected, ans, path); return ans; }

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

    for (int i=0; i<nums.length; i++) {
        if (selected[i]) {
            continue;
        }
        if (i > 0 && !selected[i-1] && nums[i] == nums[i-1]) {
            //System.out.println("cut: i->" + i + " num: " + nums[i]);
            continue;
        }
        selected[i] = true;
        path.add(nums[i]);
        dfs(nums, selected, ans, path);
        path.remove(path.size() - 1);
        selected[i] = false;
    }
}

}

hx-code commented 2 years ago

dahaiyidi commented 2 years ago

Problem

[47. 全排列 II](https://leetcode-cn.com/problems/permutations-ii/)

++

难度中等959

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

示例 1：

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

Note

排列类题目经常使用：
- used，标记是否已经访问
- 其实位置start

Complexity

时间O：n×n!
空间O：n. 递归使用，used也是n

Python

C++

class Solution {
public:
    void dfs(vector<int>& nums, int depth, vector<vector<int>>& res, vector<int>& path, vector<bool>& used){
        if(depth == nums.size()){
            res.emplace_back(path);
            return;
        }

        for(int i = 0; i < nums.size(); i++){
            // 第i已经使用过，则跳过
            // 如果nums[i] == nums[i - 1]， 且nums[i - 1]还没有被使用过
            if(used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])){
                continue;
            }
            used[i] = true;
            path.emplace_back(nums[i]);
            dfs(nums, depth + 1, res, path, used);
            used[i] = false;
            path.pop_back();            
        }

    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> path;
        vector<bool> used(nums.size(), false);
        // 避免重复必备
        sort(nums.begin(), nums.end()); 
        dfs(nums, 0, res, path, used);
        return res;
    }
};

From : https://github.com/dahaiyidi/awsome-leetcode

tian-pengfei commented 2 years ago

class Solution {

    vector<vector<int>> ans;
    unordered_set<string> is_has;
    vector<int> single_re;
    vector<int> is_visited;

public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        int size = nums.size();
        is_visited.resize(size);
        dfs(0,size,nums);
        return ans;
    }

    void dfs(int level,int size,vector<int> & nums){
        if(level==size){
            string key = getKey(single_re);
            if(is_has.find(key)==is_has.end()){
                ans.emplace_back(single_re);
                is_has.insert(key);
            }
            return ;
        }
        for (int i =0;i<size;i++) {
            if(is_visited[i])continue;
            single_re.push_back(nums[i]);
            is_visited[i]=1;
            dfs(level+1,size,nums);
            is_visited[i]=0;
            single_re.pop_back();
        }
    }
    string getKey(vector<int> &ve){
        string key = "";
        for (auto val:ve) {
            key+=("_"+to_string(val));
        }
        return key;
    }
};

tian-pengfei commented 2 years ago


class Solution {
    vector<vector<int>> re;
    vector<int> visited;
    int n;
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {

        n= nums.size();
        vector<int> tmp;
        visited.resize(n);
        sort(nums.begin(),nums.end());
        dfs(nums,tmp, 0);
        return re;

    }

    void dfs(vector<int>& nums,vector<int> tmp, int pos){
        if(pos==n){
            re.push_back(tmp);
            return ;
        }

        for (int i = 0; i < n; ++i) {
//            !visited[i-1] 表明量可能，一种是之前已经加入过了，第二种因为在这个位置就没有加入
            if((visited[i])||(i>0&&nums[i]==nums[i-1]&&!visited[i-1])){
                continue;
            }
            visited[i]=1;
            tmp.push_back(nums[i]);
            dfs(nums,tmp,pos+1);
            visited[i]=0;
            tmp.pop_back();
        }
    }
};

charlestang commented 2 years ago

思路

回溯法。

显然，这是一个全排列问题，答案的 n! 个。
每次选出一个数字，第一次有 n 个选择，第二次 n-1 个，……，第 n 次只有 1 个选择。
如果所有的数字不同，则到这里就做完了，很单纯，但是现在题目说有重复的数字，最后的排列要去除完全重复的排列。
重点关注如何去重，我可以将所有数字排序。第一个数字有 n 个选择，如果其中一个选择是数字 a，如果数组里有两个 a，那么另一个选择也是 a 的话，最后结果肯定会出现重复。所以，我们引入一个变量，如果发现在这一轮次里，我们挑中的一个数字前一轮选过，则肯定会出现重复的排列。这里应该进行剪枝。

时间复杂度：O(n!)

代码

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

        def dfs(cnt: int, s: List[int]):
            if cnt == len(nums):
                res.append(s)
            else:
                last = 100
                for i in range(n):
                    if visited[i]: continue
                    if nums[i] == last: continue
                    last = nums[i]
                    visited[i] = True
                    dfs(cnt + 1, s + [nums[i]])
                    visited[i] = False
        dfs(0, [])
        return res

GaoMinghao commented 2 years ago

public List<List<Integer>> 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<Integer>> res, List<Integer> 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);
        }
    }
}

zzzpppy commented 2 years ago

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        backtracking(nums,used);
        return res;
    }
    void backtracking(int[] nums, boolean[] used) {
        if(path.size() == nums.length) {
            res.add(new ArrayList(path));
            return;
        }
        for(int i = 0; i < nums.length; i++) {
            if(i > 0 && nums[i] == nums[i-1] && used[i-1] == false) {
                continue;
            } 
            if(used[i] == false) {
                used[i] = true;
                path.add(nums[i]);
                backtracking(nums, used);
                path.remove(path.size() - 1);
                used[i] = false;
            }
        }
    }
}

fornobugworld commented 2 years ago

class Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]: nums.sort() res=[] temp=[] def back(nums,temp): if not nums: res.append(temp) return else: for i in range(len(nums)): if i>0 and nums[i]==nums[i-1]: continue back(nums[:i]+nums[i+1:],temp+[nums[i]]) #这种拼接方法是天然的标记，判断前一字符是否在循环里。 back(nums,temp) return res

for123s commented 2 years ago

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

    void dfs(vector<int> nums, int l, int r)
    {
        if(l==r)
        {
            res.push_back(nums);
            return;
        }
        for(int i=l;i<=r;i++)
        {
            if(i!=l&&nums[l]==nums[i])
                continue;
            swap(nums[i],nums[l]);
            dfs(nums,l+1,r);
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        dfs(nums,0,nums.size()-1);
        return res;
    }
};

youzhaing commented 2 years ago

code

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def backtrack(l1, nums, check):
            if len(l1) == len(nums):
                self.res.append(l1)
                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
                backtrack(l1+[nums[i]], nums, check)     
                check[i] = 0   
        nums.sort()
        self.res = []
        check = [0 for i in range(len(nums))]
        backtrack([], nums, check)
        return self.res

taojin1992 commented 2 years ago

/*
Note: visited array, always start from 0, check nums[i-1] == nums[i] as well as visited[i-1]

## Evaluation: 

n = nums.length

## Time:

we have n! permutations (assume there are no duplicates, worst case), n! = number of leaves in our recursion tree. For each permutation, we need to copy and paste the curList of length n into the result, therefore, O(n! * n)
+

total number of nodes in the tree: depth n * max nodes in one level (n!)

+ O(nlogn)

= O(nlogn) + O(n! * n)

## Space:
stack depth: O(n)
visited array (boolean): O(n)
curList max/final len: O(n)
output: O(n! * n) numbers

sum up to O(n! * n). 

*/

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        boolean[] visited = new boolean[nums.length];
        dfs(nums, res, new ArrayList<Integer>(), visited);
        return res;
    }

    private void dfs(int[] nums, List<List<Integer>> res, List<Integer> status, boolean[] visited) {
        if (status.size() == nums.length) {
            res.add(new ArrayList<>(status));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            // 0 1 2 3 4
            // 2 2 3 3 3
            if (i >= 1 && nums[i] == nums[i-1] && visited[i - 1]) {
                continue;
            }
            if (!visited[i]) {
                status.add(nums[i]);
                visited[i] = true;
                dfs(nums, res, status, visited);
                status.remove(status.size() - 1);
                visited[i] = false;
            }
        }

    }
}

baddate commented 2 years ago

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

falconruo commented 2 years ago

思路:

回溯算法

复杂度分析:

时间复杂度: O(N!)，N为数组nums的长度, 全排列的复杂度O(N!)
空间复杂度: O(N), 辅助数组perm的大小

代码(C++):

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> res;
        vector<int> perm, used(n, 0);
        sort(nums.begin(), nums.end());
        backTracking(nums, perm, used, res);
        return res;
    }
private:
    void backTracking(vector<int>& nums, vector<int>& perm, vector<int>& used, vector<vector<int>>& res) {
        if (perm.size() == nums.size()) {
            res.push_back(perm);
            return;
        }

        for (int i = 0; i < nums.size(); ++i) {
            if (used[i] || i > 0 && nums[i] == nums[i - 1] && used[i - 1]) continue;
            used[i] = 1;
            perm.push_back(nums[i]);
            backTracking(nums, perm, used, res);
            perm.pop_back();
            used[i] = 0;
        }
    }
};

zhangzz2015 commented 2 years ago

思路

采用回溯方法，利用visit flag 表明已经选择的num，另外需要考虑在同层，要skip掉前一个相同的number。需要提前进行排序，时间复杂度为(n*2^n)，空间复杂度为O(n)

关键点

代码

语言支持：C++

C++ Code:


class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) { 

        sort(nums.begin(), nums.end());
        vector<int> onePath; 
        vector<vector<int>> ret; 
        vector<bool> visit(nums.size(), false); 
        backTrack(nums, visit, onePath, ret); 

        return ret;         
    }

    void backTrack(vector<int>& nums, vector<bool>& visit, vector<int>& onePath, vector<vector<int>>& ret)
    {
        if(onePath.size()==nums.size())
        {
            ret.push_back(onePath); 
            return;             
        }

        for(int i=0; i< nums.size(); i++)
        {
            if(visit[i])  continue; 
            if(i>0 && nums[i]==nums[i-1] && visit[i-1]==false) continue; 
            visit[i] = true; 
            onePath.push_back(nums[i]); 
            backTrack(nums, visit, onePath, ret); 
            onePath.pop_back(); 
            visit[i] = false; 
        }                
    }

};

Myleswork commented 2 years ago

思路

和组合问题Ⅱ差不多，有重复元素，需要去重。但是两题又有不一样，组合问题Ⅱ不能每次都从头开始遍历，所以需要start控制遍历起始点，但全排列Ⅱ需要从头开始遍历，所以需要对第一个元素做特殊处理。

代码

class Solution {
public:
    vector<bool> used;
    vector<int> cur;
    vector<vector<int>> res;
    void dfs(vector<int>& nums){
        if(cur.size()==nums.size()){
            res.push_back(cur);
            return;
        }
        for(int i=0;i<nums.size();i++){
            if(i!=0&&nums[i]==nums[i-1]&&used[i-1]==false) continue;
            if(used[i]==false){
                cur.push_back(nums[i]);
                used[i]=true;
                dfs(nums);
                cur.pop_back();
                used[i]=false;
            }
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        int len=nums.size();
        sort(nums.begin(),nums.end());
        used.resize(len,false);
        dfs(nums);
        return res;
    }
};

复杂度分析

时间复杂度：指数级

空间复杂度：O(n) 递归栈

leetcode-pp / 91alg-6-daily-check

【Day 82 】2022-03-03 - 47 全排列 II #92

47 全排列 II

入选理由

题目地址

前置知识

题目描述

思路

代码

思路

代码

Idea

Code

Complexity:

思路

思路

代码

思路

代码

复杂度分析

思考

code

complexity

res用来存放结果

思路

代码

复杂度

代码实现

复杂度分析

Problem

[47. 全排列 II](https://leetcode-cn.com/problems/permutations-ii/)

Note

Complexity

Python

C++

思路

代码

code

思路

关键点

代码

思路

代码