Given a collection of distinct integers, return all possible permutations.

Example: Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums == null || nums.length == 0) return res;
        helper(nums, res, new ArrayList<Integer>(), new HashSet<Integer>());
        return res;
    }

    private void helper(int[] nums, 
                        List<List<Integer>> res, 
                        List<Integer> clist, 
                        HashSet<Integer> set) {
        if(clist.size() == nums.length) {
            res.add(new ArrayList<Integer>(clist)); //对res中List<List<Integer>>里面的List进行了实例化（arraylist）
                                                    //并且把clist中的值复制到这个arraylist中
            return;
        }

        for(int i = 0; i < nums.length; i++) {
            if(set.contains(nums[i])) continue;
            else {
                clist.add(nums[i]);
                set.add(nums[i]);
                helper(nums, res, clist, set);
                set.remove(nums[i]);
                clist.remove(clist.size() - 1);
            }
        }
    }
}

与上方法一致，只是不用set，直接用clist去check包不包含当前数
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums == null || nums.length == 0) return res;
        helper(nums, res, new ArrayList<Integer>());
        return res;
    }

    private void helper(int[] nums, 
                        List<List<Integer>> res, 
                        List<Integer> clist) {
        if(clist.size() == nums.length) {
            res.add(new ArrayList<Integer>(clist)); 
            return;
        }

        for(int i = 0; i < nums.length; i++) {
            if(clist.contains(nums[i])) continue; //用clist check包不包含当前数
            else {
                clist.add(nums[i]);
                helper(nums, res, clist);
                clist.remove(clist.size() - 1);
            }
        }
    }
}