class Solution {
    List<List<Integer>> ans;
    public List<List<Integer>> permutation(int[] nums) {
         ans = new ArrayList<>();
        if(nums == null || nums.length == 0) return ans;
        bracktrack(nums, 0);
        return ans;
    }
    private void bracktrack(int[] nums, int index) {
        if(index == nums.length) {
            List<Integer> list = new ArrayList<>();
            for(int i= 0 ; i < nums.length; i++) {
                list.add(nums[i]);
            }
            ans.add(list);
            return;
        }
        for(int i = index; i < nums.length; i++){
            if(isCanSwap(nums, index, i)) continue;
            swap(nums, index, i);
            bracktrack(nums, index + 1);
            swap(nums, index, i);

        }
    }
    private boolean isCanSwap(int[] nums, int st, int ed) {
        for(int i = st; i < ed; i++) {
            if(nums[i] == nums[ed]) return true;
        }
        return false;
    }
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}