90. Subsets II

Problem:

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.

For example,
If nums = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

3/23/2018 update
一定要把树画全并且标上index。subset和permutation不一样，subset是一直往后走的。

01/22/2018
The i > 0 check is redundant.

--------------------------------------------------------------------------------------------------------------------------
思路：
和subsets完全一样，但要考虑如何去除duplicate。画个图分析下。


上图圈起来的节点就是重复的节点。可以发现，重复的节点和自己的sibling的最后一位是一样的。所以可以在递归循环里面加入：if(nums[i] == nums[i-1] && i!=startIndex) 判断，是否重复。每一层的第一个节点的最后一位是允许和上一位数重复的。比如这个test case: [1,1]。

实现：
search(subset, i+1, res, nums)因为是DFS，递归的时候i+1是为了进入下一层。这道题要首先排序，发重复的数排到一起才能继续往下做。