PermutationsII
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2]
have the following unique permutations:
[1,1,2]
, [1,2,1]
, and [2,1,1]
.
public class Permutations {
public static void main(String[] args) {
// TODO Auto-generated method stub
}
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> totalseq=new ArrayList<List<Integer>>();
if(nums==null&&nums.length==0){
ArrayList<Integer> tmp=new ArrayList<Integer>();
totalseq.add(tmp);
return totalseq;
}
dfs(0,nums,totalseq);
return totalseq;
}
private void dfs(int index, int[] nums, List<List<Integer>> totalseq) {
// TODO Auto-generated method stub
if(index==nums.length){
ArrayList<Integer> tmp=new ArrayList<>();
for(int i=0;i<nums.length;i++){
tmp.add(nums[i]);
}
totalseq.add(tmp);
}
else{
int temp=0;
for(int j=index;j<nums.length;j++){
temp=nums[index];
nums[index]=nums[j];
nums[j]=temp;
dfs(index+1, nums, totalseq);
temp=nums[index];
nums[index]=nums[j];
nums[j]=temp;
}
}
}
}
public List<List<Integer>> permuteUnique(int[] num) {
ArrayList<List<Integer>> result = new ArrayList<List<Integer>>();
permuteUnique(num, 0, result);
return result;
}
private void permuteUnique(int[] num, int start, ArrayList<List<Integer>> result) {
if (start >= num.length ) {
ArrayList<Integer> item = convertArrayToList(num);
result.add(item);
}
for (int j = start; j <= num.length-1; j++) {
if (containsDuplicate(num, start, j)) {
swap(num, start, j);
permuteUnique(num, start + 1, result);
swap(num, start, j);
}
}
}
private ArrayList<Integer> convertArrayToList(int[] num) {
ArrayList<Integer> item = new ArrayList<Integer>();
for (int h = 0; h < num.length; h++) {
item.add(num[h]);
}
return item;
}
private boolean containsDuplicate(int[] arr, int start, int end) {
for (int i = start; i <= end-1; i++) {
if (arr[i] == arr[end]) {
return false;
}
}
return true;
}
private void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
阅读(860) | 评论(0) | 转发(0) |