public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        List<Integer> curr = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        if (n == 0) return ret;
        boolean[] isVisited = new boolean[n];
        preorder(ret, nums, curr, isVisited);
        return ret;
    }

    private void preorder(List<List<Integer>> ret, int[] nums, List<Integer> curr, boolean[] isVisited) {
        if (curr.size() == nums.length) {
            ret.add(new ArrayList<Integer>(curr));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!isVisited[i]) {
                isVisited[i] = true;
                curr.add(nums[i]);
                preorder(ret, nums, curr, isVisited);
                curr.remove(curr.size() - 1);
                isVisited[i] = false;
            }
        }
    }
}
