result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        //暂存结果
        ArrayList<Integer> track = new ArrayList<>();
        //最终结果
        List<List<Integer>> result = new ArrayList<>();
        //回溯函数
        backtrack(nums, track, result);
        return result;
    }

    private void backtrack(int[] nums, ArrayList<Integer> track, List<List<Integer>> result){
        //end condition
        if(track.size() == nums.length){
            result.add(new ArrayList(track));
            return;
        }

        //【重要】每次索引都从0开始！！！这里和“所有子集”问题不同
        for(int i = 0; i < nums.length; i++){
            //用contains判断是否存在
            if(! track.contains(nums[i])){
                track.add(nums[i]);
                backtrack(nums, track, result);
                //删除容器里，最后一个索引的值
                track.remove(track.size()-1);
            }
        }
    }
}

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> track = new ArrayList<>();

        backtrack(nums, 0, track, res);

        return res;

    }

    //【重要】注意这个参数start
    private void backtrack(int[] nums, int start, List<Integer> track, List<List<Integer>> res){
        //每一个路径，都是一个解
        //【重要】这里没有明显的一个递归出口，而是靠下面的for循环的终止条件
        //【重要】因为track是公用的，所以在加入res前，需要复制一份新的
        res.add(new ArrayList(track));
        
        //每次递归不是从0开始，而是start
        for(int i = start; i < nums.length; i++){
            //重要】i 已经放在了track暂时解中，因此在此前提下，之后的递归就要exclude这个i，那就i+1即可
            track.add(nums[i]);
            //System.out.println("track add " + nums[i]);
            backtrack(nums, i+1, track, res);
            track.remove(track.size() - 1);
        }

    }
}