78.subsets & 90.subests ii & 89.graycode

[HanchengZhao]

78.subsets 90.subests ii 89.graycode

these 3 problems can be solved using similar iteration solutions

[HanchengZhao]

For 78:

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        """
        every element can be or not be in a subset, so there are totally
        2^n combinations. We can start from the 1st element and add lists that with
        it or without it, and iterate each elements.
        if the nums = [1,2,3] the process could be [[]] -> [[],[1]] -> [[],[1],[2],[1,2]]
        -> [[],[1],[2],[1,2], [3],[1,3],[2,3],[1,2,3]]
        """

        if not nums:
            return [[]]
        res = [[]]
        index = 0
        while index < len(nums):
            res +=  [i + [nums[index]] for i in res]
            index += 1
        return res

For 90:

class Solution(object):
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        '''
        almost same idea as 78.subsets, just to sort the list and check whether
        already in result everytime to remove duplicates
        '''
        if not nums:
            return [[]]
        nums.sort()
        res = [[]]
        index = 0
        while index < len(nums):
            nextarray = []
            for i in res:
                if (i + [nums[index]]) not in res:
                    nextarray.append(i + [nums[index]])
            res +=  nextarray
            index += 1
        return res

Ideas about 89.graycode can be found in issue11