90. SubsetII

# 90. SubsetII
# 这道题的思路 is similar with the subsetI, the only difference is in this question the duplicate number
#             is in the original array.
def backtrackSubsetDup(nums, idx, temp, res):
    res.append(temp)
    for i in range(idx, len(nums)):
        if i > idx and nums[i] == nums[i-1]: # to skip the duplicate number “i > idx" is garente the i-1 will
                                             # will not out the index limitation.
            continue
        backtrackSubsetDup(nums, i+1, temp+[nums[i]], res)

    return


def subsetWithDup(nums):
    res = []
    nums.sort()
    backtrack(nums, 0, [], res)
    return res