在上一篇文章 算法模式：回溯 介绍一种“一步三回头”、“落棋有悔”的算法模式：回溯。本篇文章，介绍一种无需“一步三回头”，无需“落棋有悔”也可以解决排列组合问题的算法模式：子集。
子集
超级多的编程面试问题都会涉及到排列和组合问题。一般都是使用回溯来解决该类问题，回溯法属于 深度优先搜索。子集问题模式讲的是用 广度优先搜索 来处理这些问题。子集模式适用于子集与全排列。下面分别介绍：
处理子集问题
-
我们从空集开始：[[]]
-
把第一个数 1，加到之前已经存在的集合中：[[], [1]];
-
把第二个数 5，加到之前的集合中得到：[[], [1], [5], [1,5]];
-
再加第三个数 3，则有：[[], [1], [5], [1,5], [3], [1,3], [5,3], [1,5,3]].
如果原有集合中存在重复元素，那么就需要针对这种情况特殊处理一下。流程如下：
-
先对原有集合进行排序： [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]]。方案通过 ✅
