LeetCode：46.全排列

跟着carl学算法，本系列博客仅做个人记录，建议大家都去看carl本人的博客，写的真的很好的！
代码随想录

LeetCode：46.全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1]
输出：[[1]]

这里需要注意和以前写过的那些组合问题去重方式要区分下

	public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtracking(nums, new HashSet<>(), new ArrayList<>(), res);
        return res;
    }

    private void backtracking(int[] nums, Set used, List<Integer> path, List<List<Integer>> res) {
        if (path.size() == nums.length) {
            res.add(new ArrayList(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used.contains(nums[i]))
                continue;
            path.add(nums[i]);
            used.add(nums[i]);
            // 注意这里是的 index 并不是i 或者 i + 1, 而是要从头重新开始，
            // 所以要传index，所以这里可以不要index这个参数直接传0
            // backtracking(nums, index, used, path, res);
            backtracking(nums, used, path, res);
            path.removeLast();
            used.remove(nums[i]);
        }
    }

这题里面因为nums不包含重复元素，所以也可以不使用used，可以直接使用path来进行判断

	public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtracking(nums, new ArrayList<>(), res);
        return res;
    }

    private void backtracking(int[] nums, List<Integer> path, List<List<Integer>> res) {
        if (path.size() == nums.length) {
            res.add(new ArrayList(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (path.contains(nums[i]))
                continue;
            path.add(nums[i]);
            backtracking(nums, path, res);
            path.removeLast();
        }
    }