Leetcode - 46. 全排列

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        
        // 一个数字只能被使用一次，因此用used[i]来表示nums[i]是否已经被使用
        boolean[] used = new boolean[nums.length];

        // permute用于临时存放某个排列中的数字；即按顺序记录被选中的数字
        LinkedList<Integer> permute = new LinkedList<>();
        
        // 回溯法
        backtrack(nums, used, permute, ret);
        return ret;
    }

    // 从nums中找到一个数字添加到permute中；如果permute元素个数足够，则将list复制一份添加到ret中
    // used[i]表示nums[i]是否已经被添加到了list中
    private static void backtrack(int[] nums, boolean[] used, LinkedList<Integer> permute, List<List<Integer>> ret){

        // 如果permute元素个数已经足够，则将其复制一份添加到ret中并返回
        if (permute.size() == nums.length) {
            ret.add(new ArrayList(permute));
            return;
        }

        // 如果个数不够，则看nums中哪个数字还没被使用，依次把没被使用的数字添加到permute中
        for (int i = 0; i < nums.length; i++) {
            
            // 如果已被使用，则跳过
            if (used[i]) {
                continue;
            }
            
            // 如果未被使用，则添加进去并标记为已被使用
            permute.offerLast(nums[i]);
            used[i] = true;

            // 继续调用本方法，往permute添加元素
            backtrack(nums, used, permute, ret);

            // 回溯
            permute.pollLast();
            used[i] = false;
        }
    }
}