Permutations II

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

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Thoughts

和subsets-ii处理思路是一致的. 同样是要把不是一层的相同数字考虑进来, 而把是同一层的相同数字忽略. 如果nums 是[1, 1, ..., 1, 2], 那么在第一层时引入第一个[1], 那么接下来的所有1都不应该作为第一层, 全部skip. 在第二层可以引入第二个1, 那么第三个和第N个1都不该在第二层出现了, 可以全部跳过. 以此类推.

那么我们是否可以用一个map, 记录在哪层访问过哪个数字, 以后再到那层时跳过他们不就好了. 错, 因为每层能引入谁是针对当前path来说的, 而不是全局. 拿[1, 1, 2]举例子. 在得到[1, 1, 2]和[1, 2, 1]后, 如果用全局记录我们就无法再得到[2, 1, 1]了. 因为1已经出现在过第二个位置上了.

Code

class Solution {
    private void helper(int[] nums, boolean[] visited, List<Integer> path, List<List<Integer>> res) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<Integer>(path));
        }

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

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

Analysis

时间复杂度还是O(N!), 空间O(N).