EASY TO UNDERSTAND | PYTHON | BACKTRACK | 99% RUNNING TIME
Intuition\n Describe your first thoughts on how to solve this problem. \nTo generate all possible subsets of a given list of integers, ensuring no duplicate sub
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo generate all possible subsets of a given list of integers, ensuring no duplicate subsets, we can use a backtracking approach. Sorting the array first helps in easily skipping duplicates during the subset generation process.\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nSort the Input: Sorting the array helps in handling duplicates efficiently.\nBacktracking: Use a backtracking approach to explore all possible subsets.\nStart with an empty subset and iteratively add elements.\nUse an index to keep track of the current position in the array.\nSkip duplicate elements to ensure no duplicate subsets are added.\nTrack Subsets: Maintain a list to store all unique subsets generated during the backtracking process.\n\n# Complexity\n- Time complexity:O(2 \nn\n \u22C5n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(2 \nn\n \u22C5n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution(object):\n    def subsetsWithDup(self, nums):\n        """\n        :type nums: List[int]\n        :rtype: List[List[int]]\n        """\n        # return all posible subset\n        # MUST NOT contain Duplicate\n        ret = []\n        n = len(nums)\n        nums.sort()\n        def backtrack(index, combination):\n            if combination not in ret:\n                ret.append(combination)\n\n            for i in range(index, n):\n                subCombination = combination + [nums[i]]\n                backtrack(i + 1, subCombination) \n\n        backtrack(0, [])\n        return ret\n```\n\n![cute_hug.jpg](https://assets.leetcode.com/users/images/ae881264-caee-447a-985f-6f29077f413d_1721672820.6485004.jpeg)\n
['Python']