LeetCode (Python): 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],
  []
]

Solution:

class Solution:
    # @param num, a list of integer
    # @return a list of lists of integer
    def subsetsWithDup(self, S):
        S.sort()
        solution = [] 
        self.subsetsWithDupRec(S, 0, [], solution)
        return solution
        
    def subsetsWithDupRec(self, S, index, tempSolution, solution):
        if index== len(S):
            solution.append(list(tempSolution))
            return
        
        #Not adding this element
        i = index
        while i<len(S) and S[i]==S[index]:
            i += 1
        self.subsetsWithDupRec(S, i, tempSolution, solution)
        
        #Adding it
        tempSolution.append(S[index])
        self.subsetsWithDupRec(S, index+1, tempSolution, solution)
        tempSolution.pop()