全排列问题2 中等🌟🌟🌟
问题描述
原文链接：47. 全排列 II
给定一个可包含重复数字的序列 nums ，按任意顺序返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
提示：
1 <= nums.length <= 8-10 <= nums[i] <= 10
代码实现
Java
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
// 记录那些被访问过的元素
boolean[] visited = new boolean[nums.length];
backTrack(nums, visited);
return res;
}
void backTrack(int[] nums, boolean[] visited){
// 结束条件
if(temp.size() == nums.length){
res.add(new ArrayList<>(temp));
return;
}
for(int i = 0; i < nums.length; i++){
// 去掉重复
if(i > 0 && nums[i] == nums[i-1] && visited[i-1] == false){
continue;
}
// 判断以前是否被访问过
if(visited[i] == true){
continue;
}
// 开始处理
visited[i] = true;
temp.add(nums[i]);
backTrack(nums, visited);
// 撤销之前的操作
visited[i] = false;
temp.remove(temp.size() - 1);
}
}
}
Python
class Solution(object):
def permuteUnique(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
temp = []
nums.sort()
visited = [False] * len(nums)
self.backTrack(nums, visited, temp, res)
return res
def backTrack(self, nums, visited, temp, res):
# 结束条件
if len(temp) == len(nums):
res.append(list(temp))
return
for i in range(len(nums)):
# 去掉重复
if i > 0 and nums[i] == nums[i - 1] and not visited[i - 1]:
continue
# 判断以前是否被访问过
if visited[i]:
continue
# 开始处理
visited[i] = True
temp.append(nums[i])
self.backTrack(nums, visited, temp, res)
# 撤销之前的操作
visited[i] = False
temp.pop()
C++
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> res;
vector<int> temp;
sort(nums.begin(), nums.end());
vector<bool> visited(nums.size(), false);
backTrack(nums, visited, temp, res);
return res;
}
void backTrack(vector<int>& nums, vector<bool>& visited, vector<int>& temp, vector<vector<int>>& res) {
// 结束条件
if (temp.size() == nums.size()) {
res.push_back(temp);
return;
}
for (int i = 0; i < nums.size(); i++) {
// 去掉重复
if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {
continue;
}
// 判断以前是否被访问过
if (visited[i]) {
continue;
}
// 开始处理
visited[i] = true;
temp.push_back(nums[i]);
backTrack(nums, visited, temp, res);
// 撤销之前的操作
visited[i] = false;
temp.pop_back();
}
}
};
Go
func permuteUnique(nums []int) [][]int {
res := [][]int{}
temp := []int{}
sort.Ints(nums)
visited := make([]bool, len(nums))
backTrack(nums, visited, &temp, &res)
return res
}
func backTrack(nums []int, visited []bool, temp *[]int, res *[][]int) {
// 结束条件
if len(*temp) == len(nums) {
copyTemp := make([]int, len(*temp))
copy(copyTemp, *temp)
*res = append(*res, copyTemp)
return
}
for i := 0; i < len(nums); i++ {
// 去掉重复
if i > 0 && nums[i] == nums[i-1] && !visited[i-1] {
continue
}
// 判断以前是否被访问过
if visited[i] {
continue
}
// 开始处理
visited[i] = true
*temp = append(*temp, nums[i])
backTrack(nums, visited, temp, res)
// 撤销之前的操作
visited[i] = false
*temp = (*temp)[:len(*temp)-1]
}
}