46. Permutations

问题
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

回溯，建立搜索树。
每次遍历nums中的元素。
如果未遍历过该元素，则向链表及set中添加。
向下递归，链表长度达到nums的长度时返回。
然后从set和链表中移除上一个值，回溯到上一个节点。

class Solution {
    List<List<Integer>> ans;
    HashSet<Integer> set;
    public List<List<Integer>> permute(int[] nums) {
        ans = new ArrayList();
        set = new HashSet();
        backTrack(new LinkedList(), nums, nums.length, nums.length);
        return ans;
    }
    
    private void backTrack(LinkedList<Integer> list,int[] nums, int n, int k){
        if(k == 0){
            ans.add(new ArrayList(list));
            return;
        }
        for(int i = 0; i < n ; i++){
            if(!set.contains(nums[i])){
                list.add(nums[i]);
                set.add(nums[i]);
                backTrack(list, nums , n, k-1);
                set.remove(nums[i]);
                list.removeLast();
            }
        }
    }
}