动态规划
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
permute(nums , 0 , nums.length -1, result);
return result;
}
public void permute(int[] nums , int l , int h,List<List<Integer>> ls)
{
if(l == h)
{
List<Integer> ans = new ArrayList<>();
for(int i : nums)
{
ans.add(i);
}
ls.add(ans);
return;
}
else
{
for(int i = l ; i <= h ; i ++ )
{
swap(nums,i,l);
permute(nums,l+1,h,ls);
swap(nums,l,i);
}
}
}
public void swap(int[] nums , int f , int t)
{
int temp = nums[f];
nums[f] = nums[t];
nums[t] = temp;
}
}
- 全排列 II
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
Arrays.sort(nums);
boolean[] isuser = new boolean[nums.length];
List<Integer> res = new ArrayList<>();
permute(nums , isuser , nums.length -1 , ans,res);
return ans;
}
public void permute(int[] nums , boolean[] isuser ,int h , List<List<Integer>> ans , List<Integer> res)
{
if(res.size() == nums.length )
{
ans.add(new ArrayList<>(res));
return;
}
else
{
for(int i = 0 ; i <= h ; i++)
{
if(i != 0 &&nums[i] == nums[i-1] && isuser[i-1] == false) continue;
if(isuser[i] == true)continue;
isuser[i] = true;
res.add(nums[i]);
permute(nums,isuser,h,ans,res);
res.remove(res.size()-1);
isuser[i] = false;
}
}
}
public void swap(int[] nums , int j , int t)
{
int temp = nums[j];
nums[j] = nums[t];
nums[t] = temp;
}
}