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).