How to return the list of all the Subset of a list of integer, using Python?

Question

I have been given an integer array A, I need to return an array of all it's subset. I have tried to solve this problem using Backtracking.

def subset_helper(index, result, A, temp):
    result.append(temp)
    #print(temp)
    for i in range(index,len(A)):
        temp.append(A[i])
        subset_helper(i+1,result,A,temp)
        #backtracking
        temp.pop()
    return    
def subsets(A):
    result = []
    temp = []
    index = 0
    subset_helper(index, result, A, temp)
    return result

This returns me an Empty list. Printing temp gives me right answer, but the problem asks me to return an array. I Guess the temp array due to call by reference is getting changed at each iteration and that's probably the reason it's giving me list of empty list.

Input : [12,13]
Expected Output : [[],[12],[12,13],[13]]
My Output : [[],[],[],[]]

Python Bang · Accepted Answer · 2020-03-20 06:52:35Z

3

You can use the powerset to get the output you are looking for.

iterable=[12,13]
res=list(powerset(iterable))

answered Mar 20, 2020 at 6:52

Python Bang

4827 silver badges20 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Zhubei Federer · Accepted Answer · 2020-03-20 07:10:43Z

you can try to print address in subset_helper, and you can found that your temp is the same object address, that's why your result is a list of same object value:

def subset_helper(index, result, A, temp):
    result.append(temp)
    print(id(temp))
    for i in range(index,len(A)):
        temp.append(A[i])
        subset_helper(i+1,result,A,temp)
        #backtracking
        temp.pop()
    return

output:

1559293711304
1559293711304
1559293711304
1559293711304
[[], [], [], []]

now, changes to append the copy of your tmp object:

import copy
def subset_helper(index, result, A, temp):
    result.append(copy.copy(temp))
    for i in range(index,len(A)):
        temp.append(A[i])
        subset_helper(i+1,result,A,temp)
        #backtracking
        temp.pop()
    return

and now you append an new object to result list, you can see the output as you expected :

[[], [12], [12, 13], [13]]

Bunny Rabbit · Accepted Answer · 2020-03-20 07:12:31Z

1

If it is not a homework problem, you can use the excellent itertools module to generate the subsets

from itertools import combinations, chain

def get_subsets(integers):
    return list(chain.from_iterable([combinations(integers, i) for i in range(len(integers) + 1)]))

Input: get_subsets([1, 2, 3])
Output: [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

answered Mar 20, 2020 at 7:12

Bunny Rabbit

8,44117 gold badges71 silver badges109 bronze badges

Comments

Igor F. · Accepted Answer · 2020-03-20 07:28:05Z

0

Also, from an algorithmic point of view, you can go through all possible binary numbers up to 2**N (N being the length of your set), and take 1 as indicating that the element should belong to the subset:

A = ["A", "B", "C"]

allSubsets = []
for i in range(2**len(A)):
  n = 1
  subset = []
  for j in range(len(A)):
    if i & n != 0:
      subset.append(A[j])
    n <<= 1
  allSubsets.append(subset)

print(allSubsets)

produces:

[[], ['A'], ['B'], ['A', 'B'], ['C'], ['A', 'C'], ['B', 'C'], ['A', 'B', 'C']]

answered Mar 20, 2020 at 7:28

Igor F.

2,7092 gold badges34 silver badges42 bronze badges

Collectives™ on Stack Overflow

How to return the list of all the Subset of a list of integer, using Python?

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related