41 回溯算法解含有重复数字的全排列II

问题描述：给定一个包含重复数字的序列nums，按照任意顺序返回所有不重复的全排列

回溯求解思路：首先将nums序列进行排序，并定义一个Boolean数组用于检验该元素是否选取过，每次回溯算法的时候选取一个没有被选取过的元素，并使其标记为选择，加入List<Integer>中，并进入下一级回溯算法，返回之后，使得当前元素标记为不选择，继续进行下一个循环。且如果当前元素与之前的元素一样大，且之前元素选择过，可以再次选择，否则不能选择，进行剪枝。

public void? traceBack(int [] nums,int []used,List<List<Integer>> list,List<Integer>tempList)
{
for(tempList.size()==nums.length())
{
list.add(new ArrayList<Integer>(tempList));
return;
}
for(int i=0;i<nums.length;i++)
{
if(used[i]==false)
{
if(nums[i]==nums[i-1]&&used[i-1]==false)
{
continue;
}else if(nums[i]==nums[i-1]&&used[i-1]==false)
{
used[i]=true;
traceBack(nums,used,list,tempList.add(nums[i]));
used[i]=false;
tempList.remove(tempList.size()-1);
}else
{
used[i]=true;
traceBack(nums,used,list,tempList.add(nums[i]));
used[i]=false;
tempList.remove(tempList.size()-1);
}
}else
{
continue;
}
}
}

public List<List<Integer>> TraceBack(int []nums)
{
Arrays.sort(nums);
Boolean?[]used=new int[nums.length];
for(int i=0;i<used.length;i++)
{
used=false;
}
List<List<Integer>> res=new ArrayList<>();
traceBack(nums,used,res,new ArrayList<Integer>());
return res;
}