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

Analysis: 这道题跟N-Queens，Sudoku Solver，Combination Sum，Combinations, Subsets, Generate Parentheses等一样，也是一个NP问题。

又是把所有满足条件的结果存到一个ArrayList里面，之前也有类似的如Letter combination of a Phone Number这道题。这种类型的题其实形成了一个套路，套路就是，recursion参数包括最终结果的集合（ArrayList），input（String），递归层次level（int），某一条具体的路径Path，当前外部环境

一般来说是：ArrayList<ArrayList<>>, ArrayList<>, input, 当前外部环境（可以是sum remain, 可以如本例是visited过的数组元素），递归层次level（int）

第二遍的做法：

public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> element = new ArrayList<Integer>();
        boolean[] visited = new boolean[num.length];
        helper(num, result, element, visited);
        return result;
    }
    
    public void helper(int[] num, ArrayList<ArrayList<Integer>> result, ArrayList<Integer> element, boolean[] visited){
        if (element.size() == num.length){
            // duplicate element and add it to result (element would be changed from time to time. If directly use element
            // only result would be changed when element changed)
            result.add(new ArrayList<Integer>(element)); 
            return;
        }
        
        for(int i=0; i<num.length; i++){
            if(!visited[i]){
                visited[i] = true;
                element.add(num[i]);
                helper(num, result, element, visited);
                
                // After providing a complete permutation, pull out the last number, 
                element.remove(element.size()-1);
                visited[i] = false;
            }
        }
    }
}

Li Shi的 iterative 做法（还未深究）

 1 public class Solution {
 2     public List<List<Integer>> permute(int[] num) {
 3         int len = num.length;
 4         List<List<Integer>> resSet = new ArrayList<List<Integer>>();
 5         List<Integer> curSeq = new ArrayList<Integer>();
 6         boolean[] used = new boolean[len];
 7         Arrays.fill(used,false);
 8         Arrays.sort(num);
 9         int curIndex = 0;
10         curSeq.add(-1);
11         while (curIndex!=-1){
12             if (curIndex==len){
13                 List<Integer> temp = new ArrayList<Integer>();
14                 for (int i=0;i<curSeq.size();i++) temp.add(num[curSeq.get(i)]);
15                 resSet.add(temp);
16                 curIndex--;
17                 continue;
18             }
19             
20             int val = -1;
21             if (curSeq.size()>curIndex){
22                 val = curSeq.get(curIndex);
23                 if (val!=-1)
24                     used[val]=false;
25                 curSeq.remove(curIndex);
26             }
27 
28             boolean find = false;
29             for (int i=val+1;i<len;i++)
30                 if (!used[i]){
31                     used[i]=true;
32                     curSeq.add(i);
33                     curIndex++;
34                     find = true;
35                     break;
36                 }
37             
38             if (find)
39                 continue;
40             else 
41                 curIndex--;
42         }
43 
44         return resSet;
45     }
46 }