leetcode-47. 全排列 II

JAVA解法

class Solution {
    //定义结果集
    List<List<Integer>> result = new ArrayList<>();
    //定义临时结果集
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        boolean[] used = new boolean[nums.length];
        // 将 used 全部赋值为 false
        Arrays.fill(used, false);
        // 对传进来的数组进行排序
        Arrays.sort(nums);
        // 进入回溯主体
        backTrack(nums, used);
        // 返回最终结果集
        return result;
    }

    // 实现回溯
    private void backTrack(int[] nums, boolean[] used) {
        // 当临时结果集存储的个数跟传进来的数组的长度相等时说明排序完毕
        if (path.size() == nums.length) {
            // 将排序好的结果加入结果集中
            result.add(new ArrayList<>(path));
            return;
        }
        // 开始遍历
        for (int i = 0; i < nums.length; i++) {
            // 如果同⼀树层 nums[i - 1] 使⽤过则直接跳过
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            //如果同⼀树⽀ nums[i] 没使⽤过开始处理
            if (used[i] == false) {
                //标记同⼀树⽀ nums[i] 使⽤过，防止同一树支重复使用
                used[i] = true;
                path.add(nums[i]);
                backTrack(nums, used);
                //回溯，说明同⼀树层 nums[i] 使⽤过，防止下一树层重复
                path.remove(path.size() - 1);
                used[i] = false;
            }
        }
    }
}

题解分析

  定义全局存储最终结果集和临时结果集的变量。定义一个存储布尔值的数组并全部赋值为 false，把传进来的数组排序，排序完传入回溯，得到最终答案后返回最终结果集即可。
  回溯算法传入的参数有已排序的数组和全是 false 的布尔数组。数组长度和临时结果集的长度进行比较，当临时结果集存储的个数跟传进来的数组的长度相等时说明排序完毕，若排序完毕则加入结果集，记得将临时结果集加入数组中。
  若没排序完，则对传入的待排序数组进行判断，若 nums[i] == nums[i - 1] 即当前层选择的数与上一层所选择的一样，且 used[i - 1] == false 即说明同⼀树层 nums[i - 1] 使⽤过则直接跳过，进入下一循环。如果同⼀树⽀ nums[i] 没使⽤过则开始处理，标记同⼀树⽀ nums[i] 使⽤过，防止同一树支重复使用，进入回溯，说明同⼀树层 nums[i] 使⽤过，防止下一树层重复使用，记得回溯后将当前选择移除，且设置为 false 让同层的选择不受影响。

leetcode原题：47. 全排列 II

我的博客即将同步至腾讯云+社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=3heqnkgr0co4g