题解 | #有重复项数字的全排列#

解法：选择撤销

和没有重复数字的全排列相比，选择的时候要多加一个条件

如果本轮迭代中，相同的数字已经被选择了，那么就不要选，其他情况就还是一样的

如果判断本轮迭代中相同的数字已经被选择

首先看会出现相同数字的情况, 出现相同数字的时候：num[index] == num[index - 1]， 除此之外加一个index > 0防止数组越界，

如果是在本轮迭代中，那么num[index-1]的visited标记已经被撤回了，也就是!visited[index - 1]

所以两个条件加起来就能判断在同一个迭代中，相同的数字已经被选择

具体可以看图示：

时间复杂度：f(n) = n* f(n-1),可以推断出，而f(1) = 1; 所以时间复杂度是O(n!)

空间复杂度：额外需要一个储存visited的数组O(n)，以及储存结果的数组O(n平方)，因此空间复杂度是O(n平方)

import java.util.*;
import java.util.stream.*;
import java.util.stream.Collectors;

public class Solution {
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    boolean []visited;
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        LinkedList<Integer> list = new LinkedList<Integer>();
        visited = new boolean[num.length];
        Arrays.sort(num);
        permuteUnique(num, list);
        return result;
    }

    private void permuteUnique(int[] num, LinkedList<Integer> list) {
        if (list.size() == num.length) {
            result.add(new ArrayList<Integer>(list));
            return;
        }

        for (int index = 0; index < num.length; index++) {
            if (visited[index] ||
                    (index > 0 && (num[index] == num[index - 1]) && !visited[index - 1])) {
                continue;
            }
            list.add(num[index]);
            visited[index] = true;
            permuteUnique(num, list);
            list.removeLast();
            visited[index] = false;
        }
    }

}