Two approaches in python with or without hash table


  • 0
    Z

    I try to use an hash table to record the times that each entry occurs. Then iterate through the occurrence table, to add each entry by (0 ~ times) times to existing lists. One thing to notice is use index j, rather than iterator on existing lists, because that varies, and will cause infinite loop.

    class Solution(object):
        def subsetsWithDup(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            # record occurences
            results = []
            results.append([]) # default empty, critical initialize
            occurences = {}
            for i in range(len(nums)):
            	if nums[i] not in occurences:
            		occurences[nums[i]] = 1
            	else:
            		occurences[nums[i]] += 1
            # generate subsets
            for num, times in occurences.items():
            	for j in range(len(results)): # use index than iterator, for `results` vary
            			results.append(results[j]+[num]*i)
            return results
            # run in 65 ms
    

    Another approach I learn from others is to incrementally loop over the original list, decide what to do depending on whether it is a new element or had occurred before.

    class Solution(object):
        def subsetsWithDup(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            results = []
            results.append([]) # initialize with empty, critical
            nums.sort()
            newlyAdded = 0
            for i in range(len(nums)):
            	# new element
            	if i == 0 or nums[i] != nums[i-1]:
            		newlyAdded = len(results)
            		for j in range(len(results)):
            			results.append(results[j]+[nums[i]])
            	# repeated element
            	else:
            		for j in range(len(results)-newlyAdded, len(results)):
            			results.append(results[j]+[nums[i]])
            return results
            run in 62 ms
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.