1

For example, If nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

My code is following:

class Solution(object):

"""
:type nums: List[int]
:rtype: List[List[int]]
"""
def subsets(self, nums):
    if not nums or len(nums) == 0:
        return 


    nums.sort()

    subset = []
    results = [[]]
    self.subsetHelper(nums, 0, subset, results)

    return results

def subsetHelper(self, nums, startIndex, subset, results):
    # subset is 1D list store elements that create results
    # results is 2D list that store results created

    results.append(subset)

    for i in range(startIndex, len(nums)):
        subset.append(nums[i])
        # recursion:
        self.subsetHelper(nums, i+1, subset, results)
        # backtracking:
        subset.pop()

While the answer of [1,2,3] suppose to be :

[[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]

My answer is :

[[],[],[],[],[],[],[],[],[]]

Can somebody tell me where did I go wrong, and how to modify it in order to get [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

Thanks.

Sophie
  • 77
  • 1
  • 2
  • 8

2 Answers2

1

The problem in your case is that lists are mutable.

To explain mutability briefly and how it is causing the problem, consider the following code - 

x = something # mutable type
x = y
print x
# some statement that operates on y
print x # might print something different

Now in our case, an element in result can be considered analog to x in above example and subset as y's analog. So, doing changes in subset makes changes in `result.

Solution -

Well, since our problem is caused due to list being mutable, converting subset to tuple(which is immutable) will help solve the problem. This can be done simply by changing result.append(subset) to result.append(tuple(subset)).

Finally, if you really want your result to have list instead of tuples, you can use results.append(list(tuple(subset))). This will create a lit from tuple, which will not have any relation to subset hence no hazard, due to mutability, will take place.

Extra- You might want to initialize result as result=[] instead of result=[[]]. As in later case it adds an extra empty list in your list of lists.:)

monster
  • 808
  • 10
  • 23
0

You can use this to produce all sublists of a given list:

list = [1,2,3]

def subset(i):
    finallist = []
    for first in range(0,len(i)+1):
        for last in range(first+1,len(i)+1):
            templist = []
            for index in range(first,last):
                templist.append(i[index])
            finallist.append(templist)
    return finallist


print(subset(list))

However this does not include [1,3], as this is not a true sublist. To make all possible combinations of a list, see:

Making all possible combinations of a list in python

0liveradam8
  • 752
  • 4
  • 18