题目形容
这是 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 <= 10$
- $-10 <= nums[i] <= 10$
回溯解法（Set）
因为是求所有的计划，而且数据范畴只有 $10$，能够间接用爆搜来做。
同时因为答案中不能蕴含雷同的计划，因而咱们能够先对原数组进行排序，从而确保所有爆搜进去的计划，都具备枯燥性，而后配合 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(n\log{n})$，爆搜复杂度为 $(2^n)$，每个计划通过深拷贝存入答案，复杂度为 $O(n)$。整体复杂度为 $(n \times 2^n)$
- 空间复杂度：总共有 $2^n$ 个计划，每个计划最多占用 $O(n)$ 空间，整体复杂度为 $(n \times 2^n)$
回溯解法
咱们晓得应用 Set 尽管是 $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(n\log{n})$，爆搜复杂度为 $(2^n)$，每个计划通过深拷贝存入答案，复杂度为 $O(n)$。整体复杂度为 $(n \times 2^n)$
- 空间复杂度：总共有 $2^n$ 个计划，每个计划最多占用 $O(n)$ 空间，整体复杂度为 $(n \times 2^n)$
状态压缩（Set）
因为长度只有 10，咱们能够应用一个 int 的后 $10$ 位来代表每位数组成员是否被抉择。
同样，咱们也须要先对原数组进行排序，再配合 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(n\log{n})$，爆搜复杂度为 $(2^n)$，每个计划通过深拷贝存入答案，复杂度为 $O(n)$。整体复杂度为 $(n \times 2^n)$
- 空间复杂度：总共有 $2^n$ 个计划，每个计划最多占用 $O(n)$ 空间，整体复杂度为 $(n \times 2^n)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.90 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试/面试」相干材料可拜访排版精美的 合集新基地
本文由mdnice多平台公布