Subset II

Subsets II

 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],
  []
]

------------------------- thinking --------------------------
http://bangbingsyb.blogspot.com/2014/11/leetcode-subsets-i-ii.html
------------------------ codes -----------------------------
class Solution:
    # @param num, a list of integer
    # @return a list of lists of integer
    def subsetsWithDup(self, S):
        if len(S) == 0:
            return [[]]
        S.sort()
        outs = [[]]
        start = 0
        next = 0
        #bug here, pay attention
        while start < len(S):
            if next < len(S) and S[next] == S[start]:
                next += 1
                continue
           
            insrt_eles = []
            new_outs = []
            for i in range(start, next):
                insrt_eles.append(S[start])
                for j in outs:
                    new_out = j + insrt_eles
                    new_outs.append(new_out)
            start = next
            outs = outs + new_outs
        return outs