46. 全排列

class Solution {
    private LinkedList ans = new LinkedList();
    private int n;
    private LinkedList path = new LinkedList();
    private boolean[] bool;

    public List> permute(int[] nums) {
        n = nums.length;
        bool = new boolean[n];
        dfs(nums, 0);
        return ans;
    }
    private void dfs(int nums[], int u) {
        if (u == n) {
            ans.add(path.clone());                                           //记得克隆 不然之前保存的链表都是同一个 也就是递归出来之后都是remove 同一个 这也导致答案全部都是[[],[],[],[],[],[],[]]  
        } else {
            for (int i = 0; i < n; i++) {
                if (!bool[i]) {
                    path.add(nums[i]);
                    bool[i] = true;
                    dfs(nums, u + 1);
                    bool[i] = false;
                    path.removeLast();                           //事实证明 Linked 所需要的空间大， 操作方便 而 ArrayList 空间小 而操作不方便
                }
            }
        }
    }
}