Leetcode : Permutations
Diffculty：Medium

給一個不重復(fù)的整數(shù)集合，要求返回這個集合的所有排列組合順序。
例如：
Input:
[1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

思路：
其實就是我們中學(xué)時候?qū)W過的排列組合問題。
解法的主要思路是使用回溯法，可以看做是對一個樹的遍歷。
具體的話，有兩種方式：BFS 和 DFS 也就是深度優(yōu)先和廣度優(yōu)先的遍歷方式。

BFS：
這個思路最簡單。就是每次只拿一個數(shù)，然后把這個數(shù)插入到已有數(shù)列的所有可能位置上，得到一組新數(shù)列。以此類推，一直到把最后一個插入完成得到的那組數(shù)列就是結(jié)果。
由此可知，我們最后結(jié)果個數(shù)是 (num.length-1)的階乘 個
比如現(xiàn)在有[1,2,3]。
1）們先拿1，放進去。得到的結(jié)果就是[[1]]。
2）到第二層，我們拿2。那么把2,放到[1]的可能位置，也就是一前一后。那么把2全部放進去以后，我們得到新數(shù)列[[1,2],[2,1]]
3）到第三層，拿到3，還按上面思路。3可以插入到，前中后三個位置，又有兩個數(shù)組。那么就得到了六個結(jié)果。也就是上面例子的那樣。

下面上代碼：

// leetcode 執(zhí)行結(jié)果 3ms - beats 82.59%
public static List<List<Integer>> permute_BFS(int[] nums){
        List<List<Integer>> tmpList = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        list.add(nums[0]);
        tmpList.add(list);
        List<List<Integer>> result = new ArrayList<>();
        backtrack_BFS(result, tmpList, nums, 1);
        return result;
    }

private static void backtrack_BFS(List<List<Integer>> result, List<List<Integer>> list, int[] nums, int index){
        if(index == nums.length){
            result.addAll(list);  // 如果index到底了，則把結(jié)果加到result里返回
            return;
        }else{
            List<List<Integer>> tmpList = new ArrayList<>(list.size() * (index+1));
            int tmpNum = nums[index];
            for(List<Integer> subList : list){
                for(int i=0; i<=subList.size(); i++){
                    List<Integer> innerList = new LinkedList<>(subList);
                    innerList.add(i,tmpNum);
                    tmpList.add(innerList);
                }
            }
            //  每往下一層 index+1
            backtrack_BFS(result, tmpList, nums, index+1);
        }
    }

DFS：
這個思路是深度優(yōu)先遍歷。
利用遞歸一層一層往里走，并且往tmpList里加元素，直到tmpList的長度 == nums.length 說明已經(jīng)找到了一種可能的組合。此時加到result里。并且return到上一層。
推測由于在往里添加元素時，每次都需要判斷子集合里是否已存在。所以這里會有一些耗時。時間沒有BFS短。

下面上代碼：

// leetcode 執(zhí)行結(jié)果 4ms - beats 47.75%
public static List<List<Integer>> permute_DFS(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack_DFS(result, new LinkedList<>(), nums);
        return result;
    }

private static void backtrack_DFS(List<List<Integer>> list, List<Integer> tmpList, int[] nums){
        if(tmpList.size() == nums.length){
            // 已找到一種組合結(jié)果，加都result里，返回上一層
            list.add(new ArrayList<>(tmpList));
            return;
        }else{
            for(int i=0; i<nums.length; i++){
                if(tmpList.contains(nums[i])){  // 這里拖慢了時間
                    continue;
                }
                tmpList.add(nums[i]);
                backtrack_DFS(list, tmpList, nums);

    // 這里很重要
    // 因為該元素之前固定排列的所有結(jié)果都已經(jīng)找到了。所以要移除，方便下一層找下一種組合結(jié)果。
                tmpList.remove(tmpList.size() - 1); 
            }
        }
    }