刷题06
子集
class Solution {
List> sum=new LinkedList<>();
LinkedList path=new LinkedList<>();
public List> subsets(int[] nums) {
if(nums.length==0) return sum;
backtracking(nums,0);
return sum;
}
public void backtracking(int[] nums,int startIndex)
{
sum.add(new LinkedList<>(path));
if(startIndex>=nums.length)
{
return;
}
for(int i=startIndex;i 子集Ⅱ
我可以看出在candidates[i] == candidates[i - 1]相同的情况下：
used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
used[i - 1] == false，说明同一树层candidates[i - 1]使用过
class Solution {
List> sum=new LinkedList<>();
LinkedList path=new LinkedList<>();
public List> subsetsWithDup(int[] nums) {
if(nums.length==0) return sum;
Arrays.sort(nums);
boolean[] used=new boolean[nums.length];
backtracking(nums,0,used);
return sum;
}
public void backtracking(int[] nums,int startIndex,boolean[] used)
{
sum.add(new LinkedList<>(path));
if(startIndex>=nums.length)
{
return;
}
for(int i=startIndex;i0&&nums[i-1]==nums[i]&&used[i-1]==false)
{
continue;
}
path.add(nums[i]);
used[i]=true;
backtracking(nums,i+1,used);
used[i]=false;
path.removeLast();
}
}
}
全排列
class Solution {
List> sum=new LinkedList<>();
LinkedList path=new LinkedList<>();
public List> permute(int[] nums) {
if(nums.length==0) return sum;
Arrays.sort(nums);
boolean[] used=new boolean[nums.length];
backtracking(nums,used);
return sum;
}
public void backtracking(int[] nums,boolean[] used)
{
if(path.size()==nums.length)
{
sum.add(new LinkedList<>(path));
return;
}
for(int i=0;i 全排列Ⅱ
class Solution {
List> sum=new LinkedList<>();
LinkedList path=new LinkedList<>();
public List> permuteUnique(int[] nums) {
if(nums.length==0) return sum;
Arrays.sort(nums);
boolean[] used=new boolean[nums.length];
backtracking(nums,used);
return sum;
}
public void backtracking(int[] nums,boolean[] used)
{
if(path.size()==nums.length)
{
sum.add(new LinkedList<>(path));
return;
}
for(int i=0;i0&&nums[i]==nums[i-1]&&used[i-1]==false)
{
continue;
}
//如果同?树?nums[i]没使?过开始处理
if(used[i]==false)
{
path.add(nums[i]);
used[i]=true;
backtracking(nums,used);
used[i]=false;
path.removeLast();
}
}
}
}