Subsets II @leetcode

刷题必备书籍：Cracking the Coding Interview: 150 Programming Questions and Solutions 

简历：The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍：Introduction to Algorithms
编程珠玑：Programming Pearls (2nd Edition)
C++ 学习：The C++ Programming Language, 4th Edition
经典操作系统书籍，龙书：Operating System Concepts
创业：The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career

Given a collection of integers that might contain duplicates, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

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

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

» Solve this problem

本题和permutation和subsets思路还是一样的，套路一样，注意两点：1. 避免重复 2. 避免顺序的问题

解决这两个问题用两个判断条件来解决。

Analysis: For example S = [1, 2, 2], we let S[1,2,2] as the all unduplicated subsets of [1,2,2]. Now
we have S[1,2,2] = {} + S[1] + S[2,2] + ( [1] + S[2,2] ). Then S[2, 2] = S[2] + ( [2] + S[2] ). We can observe that, S[2] is already included in S[2,2]. So we can get the rule that when S[i] == S[i-1], we skip.