学步园

Problem 1: Permutation 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].

Solve the problem on leetcode

分析：

这次，我们要生成完整的序列了，那么和上次的Subset有什么不同呢？

1. 添加进res的时间，上面题我们每添加一个数字到tmp里，就可以往res里面添加，而这次，我们要生成完整的序列，所以需要当tmp.size()＝＝序列长度的时候再往res里面添加

2. 每次不能从pos开始往数组尾巴扫了，因为我们要求的不是Subset而是完整序列，所以要从第一个数字开始往数组尾巴扫，问题又来了，我们怎么知道取没取过这个元素呢，那么我们就创建一个boolean[] visit 每此添加的时候给相对应位置置True，删去的时候置False

public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    ArrayList<Integer> tmp = new ArrayList<Integer>();
    boolean[] visit = new boolean[num.length];
    Arrays.sort(num);
    dfs(res,tmp,num,visit);
    return res;
    }
    
    public void dfs(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> tmp, int[] num, boolean[] visit){
        if(tmp.size()==num.length) {
            res.add(new ArrayList<Integer>(tmp));
            return;            
        }
        for(int i=0; i<num.length; i++){
            if(visit[i]==false){
                tmp.add(num[i]);
                visit[i] = true;
                dfs(res,tmp,num,visit);
                tmp.remove(tmp.size()-1);
                visit[i] = false;
            }
        }
    }
}

几点注意的地方：

1. 每次判断是否visit的时候，这个if语句应该概括for循环里所有的动作，因为这么想，如果visit过，我们什么事也不做，直接跳过

2. 给res添加完之后，别忘了return

Problem 2 Permutation 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].

Solve the problem on leetcode

同样的思路，有重复的数字出现在集合里，而不能生成重复的序列 

我们运用和Subset II 一样的思路，在remove后直接找到下一个和这次添加不重复的数字

public class Solution {
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    ArrayList<Integer> tmp = new ArrayList<Integer>();
    boolean[] visit = new boolean[num.length];
    Arrays.sort(num);
    dfs(res,tmp,num,visit);
    return res;
    }
    
    public void dfs(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> tmp, int[] num, boolean[] visit){
        if(tmp.size()==num.length) {
            res.add(new ArrayList<Integer>(tmp));
            return;            
        }
        for(int i=0; i<num.length; i++){
            if(visit[i]==false){
                tmp.add(num[i]);
                visit[i] = true;
                dfs(res,tmp,num,visit);
                tmp.remove(tmp.size()-1);
                visit[i] = false;
	        while(i<num.length-1 && num[i] == num[i+1]) i++;
            }
        }
    }
}