LeetCode
全排列
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例：
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
解法：回溯法
解题思路：思路很简单，因为要全排列，所以每一个数字都可能选择，即选择区间为[0,nums.length], 但是一个数字只能被选择一次，所以我们需要定义一个boolean[] used数组,长度为nums.length,又因为不能有重复的，所以一个数字的选择不能相同，我们通过这一行代码来剪枝
if(i>0 && nums[i]==nums[i-1] && !used[i-1])
continue;
当当前数字和上一个数字相同时，且上一个数字没有被使用，我们就进行剪枝
因此我们需要对数组进行排序
完整代码：
class Solution {
public List<List<Integer>> permuteUnique(int[] nums)
{
List<List<Integer>> res= new ArrayList<List<Integer>>();
if(nums.length == 0)
return res;
List<Integer> sub = new ArrayList<Integer>();
boolean[] used = new boolean[nums.length];
Arrays.sort(nums);
dfs(used, nums, 0, res, sub);
return res;
}
public void dfs(boolean[] used, int[] nums, int len, List<List<Integer>> res, List<Integer> sub)
{
if(len==nums.length) //用len来表示全排列子集的长度
{
res.add(new ArrayList<>(sub));
return;
}
for(int i=0; i<nums.length; i++) //从nums中取数字
{
if(i>0 && nums[i]==nums[i-1] && !used[i-1])//剪枝
continue;
if(!used[i])
{
used[i]=true;//置为被使用
sub.add(nums[i]);
dfs(used, nums, len+1, res, sub);
sub.remove(len);//删除
used[i]=false;//回溯
}
else
continue;
}
}
}
解法2：交换法，不用used数组
解题思路：
以[1, 2, 3]为例子，按照下面的树回溯出整个全排列：
[|1, 2, 3] -> [1|, 2, 3]
[1|, 2, 3] -> [1, 2|, 3], [2, 1|, 3]
[1, 2|, 3] -> [1, 2, 3|], [3, 2, 1|], [1, 3, 2|]
[2, 1|, 3] -> [2, 1, 3|], [3, 1, 2|], [2, 3, 1|]
ps：以[1, 2|, 3] -> [1, 2, 3|], [3, 2, 1|], [1, 3, 2|]为例，’|'往后移动一位，得到[1, 2, 3|]；[1, 2, 3|]中的3和1位置交换，得到[3, 2, 1|]；[1, 2, 3|]中的3和2交换位置，得到[1, 3, 2|]。
按照这个思路，可以解决问题
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
public class Solution {
public List<List<Integer>> permuteUnique(int[] nums)
{
List<List<Integer>> res= new ArrayList<List<Integer>>();
if(nums.length == 0)
return res;
int current_len = 0;
Arrays.sort(nums);
backtrack(res,current_len,nums);
return res;
}
public void swap(int[] nums, int a, int b)
{
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
public void backtrack(List<List<Integer>> res, int current_len, int[] nums)
{
if(current_len == nums.length)
{
List<Integer> numsl = new ArrayList<Integer>();
for(int i=0; i<nums.length; i++)
numsl.add(nums[i]);
res.add(numsl);
return;
}
current_len++;
backtrack(res,current_len,nums);
current_len--;
for(int i=0; i<current_len; i++)
{
if(nums[i] == nums[current_len])
break;
swap(nums,i,current_len);
current_len++;
backtrack(res,current_len,nums);
current_len--;
swap(nums,i,current_len);
}
}
}
解法来源于
作者：tai-yang-tian
链接：https://leetcode-cn.com/problems/permutations-ii/solution/shuang-bai-si-lu-chao-ji-jian-ji-by-tai-yang-tian/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
心得体会
感觉回溯算法还是比较简单的，现在中等难度的题已经可以比较轻松的解决了，下面会做一些困难难度的题，毕竟不能老是呆在舒适区，这样也进步不了
