Algorithm
题目: All Subsets II -- with Duplications
Given a collection of integers that might contain duplicates, return all possible subsets.Note: The solution set must not contain duplicate subsets.
我假设给的input nums[] 都是已经sort好的
For example:
If nums = [1,2,2], a solution is:
[[2],[1],[1,2,2],[2,2],[1,2],[]]
解法一: pure recursion
用pure recursion的话就比较难处理这个问题了，因为涉及到一个重复的问题。最简单的办法是用HashSet来帮助我们处理掉重复，但这样并不实际降低时间复杂度。让我们再来分析一下有duplication的情况下recursion的表格:
可以看到，从12到112这一层，新增的内容不再是12里所有的subsets，而是12中新增的subsets。这时候我们就需要在recursion里面返回或者追踪这个 新增的size 来确保我们处理duplication时的逻辑依然正确。
解法2.1: DFS (topdown)
让我们再来看一下上一题的DFS recursion tree在有重复的情况下是怎么样的:
可以发现蓝色的这两段里面有重复项，去掉其中的任意一个分支便可以了。对上一题的 解法二 做以下修改:
这就比解法一pure recursion 中要追踪一个int[] lastAdded 变量的值简单多了。
DFS的修改2
刚才做的是直接剔除一个重复的recursion分支；那么以下这个常见的做法是对 DFS recursion树 做了什么样的改变呢？这次先来看代码：
和上一种修改的思路不同，这次是利用'往后看'的思路来去重，以下是DFS recursion树结构：
红色部分为被剔除的分支，蓝色部分为新加入的分支。这个方法直接改变了树结构，而不仅仅是从把重复项从分支中剔除。新加入的分支直接把重复项给跳过了(while循环 level++)。所以，新的DFS recursion树是这样的：
解法三: 对解法二树结构的不同看法
解法三的去重方式可以和 解法二.2 的相同。但是不能用 解法二.1 的去重方式。
解法四: 另一种DFS
对于解法三的修改，也有两种常见的模式，但这两种的逻辑是一致的(产生的recursion tree一样)。
需要被剔除的是蓝色这段分支。
或者
以上，分别从四种常见的解All Subsets的方法来分析他们背后的逻辑和思路。还有一些其他的解法，比如iteration，bit operation mapping，或者是其他结构的recursion tree本篇不再赘述。
参加来offer学习的不仅仅是一些更高效的算法和好的归纳总结，更多是培养解题思路和方法，让知识结构系统化，从而提高自己分析问题的能力。而这些能力，才是面试中真正需要表现出来并且能打动面试官的。