{leetcode}/problems/subsets-ii/[LeetCode - Subsets II^]
Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: [1,2,2] Output: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
这道题跟 78. Subsets 类似。不一样的地方是要处理重复元素：
第 4 行新添加的 2 要加到第 3 行的所有解中，而第 3 行的一部分解是旧解，一部分是新解。可以看到，我们黑色部分是由第 3 行的旧解产生的，橙色部分是由新解产生的。
而第 1 行到第 2 行，已经在旧解中加入了 2 产生了第 2 行的橙色部分，所以这里如果再在旧解中加 2 产生黑色部分就造成了重复。
所以当有重复数字的时候，我们只考虑上一步的新解，算法中用一个指针保存每一步的新解开始的位置即可。
如果使用递归回溯来解决这个问题，遇到重复的直接跳过就可以了，因为重复字段已经处理过一次了。
- 一刷
-
link:{sourcedir}/_0090_SubsetsII.java[role=include] - 二刷
-
link:{sourcedir}/_0090_SubsetsII_2.java[role=include]