Python Iterative Solution


  • 0
    J
    class Solution(object):
        def subsets(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            if not nums:
                return
            subsets_prev = [[nums[len(nums)-1]]]
            subsets_cur = []
            index = len(nums)-2
            while index >= 0:
                subsets_cur = [[nums[index]]]
                for s in subsets_prev:
                    subsets_cur.append([x for x in s])
                    s.append(nums[index])
                    subsets_cur.append(s)
                subsets_prev = subsets_cur
                index -= 1
            subsets_prev.append([])
            return subsets_prev
    

    The idea is:
    subsets of num[i..N-1] is, [ num[i], subsets[i+1..N-1], num[i] join every set in subsets[i+1..N-1] ]

    We first calculate base case subsets[N-1 .. N-1], obviously, it is [ [nums[N-1]] ]. Then work backwards.


Log in to reply
 

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