【面试高频题】难度 1/5，详尽注释的超热门回溯题

题目描述

这是 LeetCode 上的 90. 子集 II ，难度为 中等。

Tag : 「位运算」、「回溯算法」、「状态压缩」、「DFS」

给你一个整数数组 nums，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：

输入：nums = [1,2,2]

输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

输入：nums = [0]

输出：[[],[0]]

提示：

• 1<=nums.length<=101 <= nums.length <= 101<=nums.length<=10
• −10<=nums[i]<=10-10 <= nums[i] <= 10−10<=nums[i]<=10

回溯解法（Set）

由于是求所有的方案，而且数据范围只有 101010，可以直接用爆搜来做。

同时由于答案中不能包含相同的方案，因此我们可以先对原数组进行排序，从而确保所有爆搜出来的方案，都具有单调性，然后配合 Set 进行去重。

代码：

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        Set<List<Integer>> ans = new HashSet<>();
        List<Integer> cur = new ArrayList<>();
        dfs(nums, 0, cur, ans);
        return new ArrayList<>(ans);
    }

    /**
     * @param nums 原输入数组
     * @param u 当前决策到原输入数组中的哪一位
     * @param cur 当前方案
     * @param ans 最终结果集
     */
    void dfs(int[] nums, int u, List<Integer> cur, Set<List<Integer>> ans) {
        // 所有位置都决策完成，将当前方案放入结果集
        if (nums.length == u) {
            ans.add(new ArrayList<>(cur));
            return;
        }

        // 选择当前位置的元素，往下决策
        cur.add(nums[u]);
        dfs(nums, u + 1, cur, ans);

        // 不选当前位置的元素（回溯），往下决策
        cur.remove(cur.size() - 1);
        dfs(nums, u + 1, cur, ans);
    }
}

• 时间复杂度：排序复杂度为 O(nlog⁡n)O(n\log{n})O(nlogn)，爆搜复杂度为 (2n)(2^n)(2n)，每个方案通过深拷贝存入答案，复杂度为 O(n)O(n)O(n)。整体复杂度为 (n×2n)(n \times 2^n)(n×2n)
• 空间复杂度：总共有 2n2^n2n 个方案，每个方案最多占用 O(n)O(n)O(n) 空间，整体复杂度为 (n×2n)(n \times 2^n)(n×2n)

回溯解法

我们知道使用 Set 虽然是 O(1)O(1)O(1) 操作，但是只是均摊 O(1)O(1)O(1)。

因此我们来考虑不使用 Set 的做法。

我们使用 Set 的目的是为了去重，那什么时候会导致的重复呢？

其实就是相同的元素，不同的决策方案对应同样的结果。

举个🌰，[1,1,1] 的数据，只选择第一个和只选择第三个（不同的决策方案），结果是一样的。

因此如果我们希望去重的话，不能单纯的利用「某个下标是否被选择」来进行决策，而是要找到某个数值的连续一段，根据该数值的选择次数类进行决策。

还是那个🌰，[1,1,1] 的数据，我们可以需要找到数值为 1 的连续一段，然后决策选择 0 次、选择 1 次、选择 2 次 ... 从而确保不会出现重复

也就是说，将决策方案从「某个下标是否被选择」修改为「相同的数值被选择的个数」。这样肯定不会出现重复，因为 [1,1,1] 不会因为只选择第一个和只选择第三个产生两个 [1] 的方案，只会因为 1 被选择一次，产生一个 [1] 的方案。

代码：

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> cur = new ArrayList<>();
        dfs(nums, 0, cur, ans);
        return ans;
    }

    /**
     * @param nums 原输入数组
     * @param u 当前决策到原输入数组中的哪一位
     * @param cur 当前方案
     * @param ans 最终结果集
     */
    void dfs(int[] nums, int u, List<Integer> cur, List<List<Integer>> ans) {
        // 所有位置都决策完成，将当前方案放入结果集
        int n = nums.length;
        if (n == u) {
            ans.add(new ArrayList<>(cur));
            return;
        }

        // 记录当前位置是什么数值（令数值为 t），并找出数值为 t 的连续一段
        int t = nums[u];
        int last = u;
        while (last < n && nums[last] == nums[u]) last++;

        // 不选当前位置的元素，直接跳到 last 往下决策
        dfs(nums, last, cur, ans);

        // 决策选择不同个数的 t 的情况：选择 1 个、2 个、3 个 ... k 个
        for (int i = u; i < last; i++) {
            cur.add(nums[i]);
            dfs(nums, last, cur, ans);
        }

        // 回溯对数值 t 的选择
        for (int i = u; i < last; i++) {
            cur.remove(cur.size() - 1);
        }
    }
}

• 时间复杂度：排序复杂度为 O(nlog⁡n)O(n\log{n})O(nlogn)，爆搜复杂度为 (2n)(2^n)(2n)，每个方案通过深拷贝存入答案，复杂度为 O(n)O(n)O(n)。整体复杂度为 (n×2n)(n \times 2^n)(n×2n)
• 空间复杂度：总共有 2n2^n2n 个方案，每个方案最多占用 O(n)O(n)O(n) 空间，整体复杂度为 (n×2n)(n \times 2^n)(n×2n)

状态压缩（Set）

由于长度只有 10，我们可以使用一个 int 的后 101010 位来代表每位数组成员是否被选择。

同样，我们也需要先对原数组进行排序，再配合 Set 来进行去重。

代码：

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        Set<List<Integer>> ans = new HashSet<>();
        List<Integer> cur = new ArrayList<>();
        
        // 枚举 i 代表，枚举所有的选择方案状态
        // 例如 [1,2]，我们有 []、[1]、[2]、[1,2] 几种方案，分别对应了 00、10、01、11 几种状态
        for (int i = 0; i < (1 << n); i++) {
            cur.clear();
            // 对当前状态进行诸位检查，如果当前状态为 1 代表被选择，加入当前方案中
            for (int j = 0; j < n; j++) {
                int t = (i >> j) & 1;
                if (t == 1) cur.add(nums[j]);
            }
            // 将当前方案中加入结果集
            ans.add(new ArrayList<>(cur));
        }
        return new ArrayList<>(ans);
    }
}

• 时间复杂度：排序复杂度为 O(nlog⁡n)O(n\log{n})O(nlogn)，爆搜复杂度为 (2n)(2^n)(2n)，每个方案通过深拷贝存入答案，复杂度为 O(n)O(n)O(n)。整体复杂度为 (n×2n)(n \times 2^n)(n×2n)
• 空间复杂度：总共有 2n2^n2n 个方案，每个方案最多占用 O(n)O(n)O(n) 空间，整体复杂度为 (n×2n)(n \times 2^n)(n×2n)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.90 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉