2023-05-17 刷题

47. 全排列 II

思路分析：

1. 将原问题转换成子问题，先不考虑重复元素，例如 P{1,2,3} = {"1" + P{2,3}, "2" + P{1,3}， "3" + P{1,2}}。之后再考虑重复元素。
2. 怎么枚举？枚举每个位置可以填哪些数。【这种枚举方式能保证字典序，除此外，还有一种，枚举每个数可以放到哪个位置上，这题不适合】
3. 怎么去重？首先对输入的数组进行排序，目的是在当前位置枚举可以使用哪些元素时，可以将相同的元素规定一个顺序。对于1 1 1 2 2 这种，重复的数，规定只能从前往后使用。visit[]数组标记每个数是否使用了。对于三个1，要使用第二个1，只有当visit[0] = true。同理，要使用第三个1，只能当visit[1] = true。 这样就能保证相同元素在所有的全排列结果中的相对顺序是唯一的。

复杂度分析：

• 时间：O(nlogn + n! * n). 对输入数组进行排序，O(nlogn), dfs递归调用，实际是枚举每个位置，反应在参数pos (也等于path.size(), 这里没有省略pos，是因为显示写出pos更易懂一点) 。因此，总共有n个位置，每个位置遍历n个元素，依次将没有使用过的元素，放在该位置上，然后进行递归调用，最后枚举到的结果，需要copy一遍到结果数组中，所以这步的时间复杂度就是：O(n! * n).
• 空间：O(n). 如果不考虑结果数组的话，中间用到的visited数组以及递归的栈最大深度n, 因此空间是O(n).

本题难点：去重。

class Solution {
    public List<List<Integer>> permuteUnique(int[] A) { // time: O(nlogn + n!*n), space: O(n)
        ans = new ArrayList<>();
        visited = new boolean[A.length];

        Arrays.sort(A);
        dfs(A, 0, new ArrayList<>());

        return ans;
    }

    List<List<Integer>> ans;
    boolean[] visited;

    void dfs(int[] A, int pos, List<Integer> path) {
        if (pos == A.length) {
            ans.add(new ArrayList<>(path));
            return;
        }
        // 枚举当前pos位置，能填哪些数
        for(int i = 0; i < A.length; i++) {
            if (visited[i] || 
                i > 0 && A[i] == A[i-1] && !visited[i - 1]
            ) {
                continue;
            }
            // 否则说明A[i]这个数可以使用
            visited[i] = true;
            path.add(A[i]);

            dfs(A, pos + 1, path);

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