Permutations & Permutations II

Permutations

Given a collection of numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

Permutations II

 

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].

 

Naive Way: 与subset不同的是，这回要将所有排列找出。应该同样有recursive 和 iterative两种方法。这里我想到了Generate Parentheses 中那个滴水不漏的做法——将新的"()"插入到原来每一个位置中。如果遇到重复，可以排序而不用set做吗？

这是iterative的做法，算法复杂度是O(n!)，需要用Set。

public class Solution {
    public List<List<Integer>> permute(int[] num) {
        List<List<Integer>> gross = new ArrayList<List<Integer>>();
        // base case
        if(num.length==0){return gross;}
        List<Integer> first_list = new ArrayList<Integer>();
        first_list.add(num[0]);
        gross.add(first_list);
        // iterative
        for(int i = 1;i < num.length;i++){
            Set<List<Integer>> set = new HashSet<List<Integer>>();
            for(int j = 0;j < gross.size();j++){
                List<Integer> list = gross.get(j);
                for(int t = 0;t <= list.size();t++){
                    List<Integer> new_list = new ArrayList<Integer>(list);
                    new_list.add(t,num[i]);
                    set.add(new_list);
                }
            }
            gross.clear();
            gross.addAll(set);
        }
        return gross;
    }
}


这是recursive的做法，比iterative要差，因为要用多很多额外的space。

public class Solution {
    public List<List<Integer>> permute(int[] num) {
        return permute(num, num.length-1);
    }
    
    private List<List<Integer>> permute(int[] num, int index){
        List<List<Integer>> gross = new ArrayList<List<Integer>>();
        Set<List<Integer>> set = new HashSet<List<Integer>>();
        // base case
        if(index < 0){return gross;}
        if(index==0){
            List<Integer> list = new ArrayList<Integer>();
            list.add(num[index]);
            gross.add(list);
            return gross;
        }
        // recursion
        List<List<Integer>> pre = permute(num, index-1);
        for(int i = 0;i < pre.size();i++){
            for(int j = 0;j <= pre.get(i).size();j++){
                List<Integer> list = new ArrayList<Integer>(pre.get(i));
                list.add(j,num[index]);
                set.add(list);
            }
        }
        gross.addAll(set);
        return gross;
    }
}