> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/02-17-2022-47.md).

# 02/17/2022 47

![](https://423021406-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-Mjjyb1BqScHCWaFFmF4%2Fuploads%2FWXu5LeCblCSkv2MaGACJ%2Fimage.png?alt=media\&token=3300b5d5-348d-43e4-af2c-1d7de0213702)

![](https://423021406-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-Mjjyb1BqScHCWaFFmF4%2Fuploads%2FKhNFFrsqwVKpCc3abGm2%2Fimage.png?alt=media\&token=2557f1a0-cd54-4cf1-8e0a-2816a1d1f9e9)

![](https://423021406-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-Mjjyb1BqScHCWaFFmF4%2Fuploads%2FgFSE4mKsrZegUYOlaCzo%2Fimage.png?alt=media\&token=16d4dddc-5b5b-4eb9-8aa5-c7256b890d49)

method:

Different from 46, in this question, the nums may contain duplicate elements. In order to avoid duplicate lists in the final result, we should sort the nums first. Then in the backtracking function, the most import thing is to check if i >0 and nums\[i] == nums\[i-1] and nums\[i-1] == false. 

Time O(n\* n!)

Space O(n)

**Note**, we did not take into account the space needed to hold the results. Otherwise, the space complexity would become O(N⋅N!).

```
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;//回溯
            }
        }
    }
}
```