AlgoPressAppearance
0047-全排列II
https://leetcode.cn/problems/permutations-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
思路
先排序，如果发现当前一个数和前面刚排序拿出来的数(used[i-1] = false)一致，就跳过 注意返回条件是 i>0 && nums[i] == nums[i-1] && used[i-1] == false
参考代码
csharp
public class Solution {
private List<IList<int>> result = new List<IList<int>>();
private bool[] used;
private void dfs(int[] nums, List<int> list){
if(list.Count == nums.Length){
result.Add(new List<int>(list.ToArray()));
return;
}
for(int i=0; i<nums.Length; i++){
if(!used[i]){
//注意这里返回条件是上一个排列的同样的数字用过了被取出
//这里同样的数字就不需要再进去拍了，比如 1,1,2 前面第一个1排过了，取出来，
//现在第二个1就不用再进去排了，排了也是和第一次一样的结果
if(i > 0 && nums[i] == nums[i-1] && used[i-1]){
continue;
}
list.Add(nums[i]);
used[i] = true;
dfs(nums,list);
list.RemoveAt(list.Count-1);
used[i] = false;
}
}
}
public IList<IList<int>> PermuteUnique(int[] nums) {
List<int> list = new List<int>();
Array.Sort(nums);
used = new bool[nums.Length];
dfs(nums,list);
return result;
}
}
复习:20220512
csharp
public class Solution {
List<IList<int>> result = new List<IList<int>>();
List<int> list = new List<int>();
bool[] used;
private void dfs(int[] nums, List<int> list){
if(nums.Length == list.Count){
result.Add(new List<int>(list));
return;
}
for(int i=0; i<nums.Length; i++){
if(used[i] || i>0 && used[i-1] && nums[i] == nums[i-1]){ //使用过的，或者和前面元素相同且前面使用过的，去重
continue;
}
list.Add(nums[i]);
used[i] = true;
dfs(nums,list);
list.RemoveAt(list.Count-1);
used[i]= false;
}
}
public IList<IList<int>> PermuteUnique(int[] nums) {
Array.Sort(nums); //排序准备去重
used = new bool[nums.Length];
dfs(nums,list);
return result;
}
}