Permutations I & Permutations II

Permutations I

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

用DFS的方法，recursive不断寻找下一个数字，用一个boolean的数组visited来记录已经访问过的数字，避免重复。在访问结束的时候，只有满足条件sublist.size() 和 num.length 相等的情况下才能拷贝sublist并加入list中间。

我出现的问题: 由于对recursive的过程不够熟悉，所以在每次loop前拷贝了当前的sublist用在下一层中， 这样会大大增加space complexity，也是完全不必要的， 因为recursive不会同时执行两个loop，所以在某层recursive结束后我们只要删除加入的数字并且修改visited情况就可以保证sublist对下次loop使用的初始化是正确的。

public List<List<Integer>> permute(int[] num) {
        
        boolean[] visited = new boolean[num.length];
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        
        for(int i = 0 ; i < num.length; i ++)
            visited[i] = false;
            
        List<Integer> subList = new ArrayList<Integer>();
        generate(list,subList, num, visited);
        
        return list;
    }
    
    private void generate(List<List<Integer>> list, List<Integer> subList, int[] num, boolean[] visited){
        
        if(subList.size() == num.length){
            
            list.add(new ArrayList<Integer>(subList));
            return;
        }
        
        
        for(int i = 0; i < num.length; i ++){
        
            if(visited[i] == false){
                
                subList.add(num[i]);
                visited[i] = true;
                generate(list, subList, num, visited);
                visited[i] = false;
                subList.remove(subList.size()-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].

和第一题类似，只是多了需要检验重复的情况。方法还是DFS，只是我们发现相同元素如果顺序的执行的话其实结果是重复的。

例如[1,1,2]
对第一个元素 先取 1, 剩下的选择就是 [1,2]
而如果从第二个元素开始 取 1, 剩下可以选择的仍然是[1,2]
这不是我们想要的情况，因此我们应该跳过连续选择相同元素的情况。

如何能保证我们不会选择同样地元素进行recursive处理呢？ 我这里用的built in 的sort 方法，保证有相同元素它们就必然相邻，这样的话，当我们对不重样的第一个元素处理完发现后面是重复元素时，我们就跳过它。

public List<List<Integer>> permuteUnique(int[] num) {
        
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        
        ArrayList<Integer> number = new ArrayList<Integer>();
        boolean visited[] = new boolean[num.length];
        
        
        for(int i = 0; i < num.length; i ++)
            number.add(num[i]);
        
        Collections.sort(number);
        List<Integer> subList = new ArrayList<Integer>();
        generate(list, subList, number, visited);
        
        return list;
        
    }
    
    private void generate(List<List<Integer>> list, List<Integer> subList, ArrayList<Integer> number, boolean[] visited){
        
        if(subList.size() == number.size()){
            List<Integer> copyList = new ArrayList<Integer>(subList);
            list.add(copyList);
            return;
        }
        
        for(int i = 0; i < number.size(); i ++){
            
            if(visited[i] == false){
                
                subList.add(number.get(i));
                visited[i] = true;
                //recurse
                generate(list, subList, number, visited);
                
                visited[i] = false;
                subList.remove(subList.size()-1);
                while(i + 1 < number.size() && number.get(i) == number.get(i+1))
                    i ++;
            }
            
        }
    
    }

把自己有疑惑的问题和想法写出来，下次遇到避免重复一样的问题。