Unique Subsets

    Example

    If S = , a solution is:

    Note

    此题在上一题的基础上加了有重复元素的情况，因此需要对回溯函数进行一定的剪枝，对于排列组合的模板程序，剪枝通常可以从两个地方出发，一是在返回结果result.add之前进行剪枝，另一个则是在处剪枝，具体使用哪一种需要视情况而定，哪种简单就选谁。

    以 [1, 2_1, 2_2] 为例，若不考虑重复，组合有 [], [1], [1, 2_1], [1, 2_1, 2_2], [1, 2_2], [2_1], [2_1, 2_2], [2_2]. 其中重复的有 [1, 2_2], [2_2]. 从中我们可以看出只能从重复元素的第一个持续往下添加到列表中，而不能取第二个或之后的重复元素。参考上一题Subsets的模板，能代表「重复元素的第一个」即为 for 循环中的变量，i == pos时，处所代表的变量即为某一层遍历中得「第一个元素」，因此去重时只需判断i != pos && s[i] == s[i - 1](不是 i + 1, 可能索引越界，而i 不等于 pos 已经能保证 i >= 1).

    和前一道题差不多，最坏情况下时间复杂度为 2^n. 空间复杂度为 O(n).