算法模式：子集
在上一篇文章 算法模式：回溯 介绍一种“一步三回头”、“落棋有悔”的算法模式：回溯。本篇文章，介绍一种无需“一步三回头”，无需“落棋有悔”也可以解决排列组合问题的算法模式：子集。
子集
处理子集问题
举例来说明一下这个模式：
给一组数字 [1, 5, 3]
我们从空集开始：
[[]]把第一个数
1，加到之前已经存在的集合中：[[], [1]];把第二个数
5，加到之前的集合中得到：[[], [1], [5], [1,5]];再加第三个数
3，则有：[[], [1], [5], [1,5], [3], [1,3], [5,3], [1,5,3]].
如果原有集合中存在重复元素，那么就需要针对这种情况特殊处理一下。流程如下：
给一组数字 [5, 1, 5]
先对原有集合进行排序：
[1, 5, 3]从空集开始：
[[]]把第一个数
1，加到之前已经存在的集合中：[[], [1]];把第二个数
5，加到之前的集合中得到：[[], [1], [5], [1,5]];处理第三个数，也是
5时需要注意：如果还是按照上述方案处理，那么就会得到如下结果：
[[], [1], [5], [1,5], [5], [1, 5], [5, 5], [1,5, 5]]。这里出现了重复子集：[5], [1, 5]。该方案不通过，❌观察最后生成的所有子集与重复的子集，会发现重复的子集，在处理第二个数时，已经处理过
[], [1]，如果再次处理5，那么就会出现重复。所以，只需要处理在处理上一个相同的数时新增加的子集即可。上一个相同数新增的子集是[5], [1,5]，只需要在这些子集后面增加当前数字即可。这样最后的子集就是：[[], [1], [5], [1,5], [5, 5], [1,5, 5]]。方案通过 ✅
处理排列问题
举例来说明一下这个模式在处理排列问题时的步骤：
给一组数字 [1, 5, 3]
把第一个数
1，集合中：[[1]];把第二个数
5，加到之前的集合中得到，由于[1, 5]和[5, 1]属于两个排列，那么就需要在所有可能的位置都增加一下，最后得到的排列如下：：[[5, 1], [1,5]];再加第三个数
3，也是如上，在所有可能的位置都增加，最终排列如下：[[3, 5, 1], [5, 3, 1],[5, 1, 3], [3, 1, 5], [1, 3, 5], [1, 5, 3]]。
思考一下：如何处理有重复元素的排列？
子集模式的适用场景：
问题需要咱们去找数字的组合或是排列
90. 子集 II
给你一个整数数组 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
思路分析
典型的子集问题，直接按照上面 处理子集问题 的步骤来实现即可：
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-04-10 11:38:25
*/
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
int length = nums.length;
List<List<Integer>> result = new ArrayList<>((int) Math.pow(2, length));
result.add(new ArrayList<>());
int start = 0;
Integer prev = null;
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
int size = result.size();
int j = 0;
// 如果与前一个元素相同，则只需要处理上次添加的子集即可
if (prev != null && num == prev) {
j = start;
}
for (; j < size; j++) {
List<Integer> subset = result.get(j);
List<Integer> ns = new ArrayList<>(subset);
ns.add(num);
result.add(ns);
}
prev = num;
start = size;
}
return result;
}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]]
提示：
1 <= nums.length <= 6-10 <= nums[i] <= 10nums中的所有整数 互不相同
思路分析
参考子集模式处理排列问题的代码框架，代码如下：
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-04-10 17:22:39
*/
public List<List<Integer>> permute(int[] nums) {
Queue<List<Integer>> result = new LinkedList<>();
result.offer(new ArrayList<>(List.of(nums[0])));
for (int i = 1; i < nums.length; i++) {
int num = nums[i];
int size = result.size();
for (int j = 0; j < size; j++) {
List<Integer> tmp = result.poll();
for (int k = 0; k <= tmp.size(); k++) {
List<Integer> adding = new ArrayList<>(tmp);
if (k == tmp.size()) {
adding.add(num);
} else {
adding.add(k, num);
}
result.offer(adding);
}
}
}
return new ArrayList<>(result);
}有一个地方需要注意：请对比子集模式在处理子集和排列时的不同：
子集直接在结果中添加新子集；
排列则是将结果中的元素出队，添加新元素后，再入队。
| 感兴趣的小伙伴，可以本文解法与在 算法模式：回溯 中，使用回溯模式的解法，进行一个对比。 |
