CODEWITHSUNDEEP
pythonalgorithmrecursion
user3245453
user3245453

Reputation: 261

Subset sum with `itertools.combinations`

I have a list of integers in python, let's say:

weight = [7, 5, 3, 2, 9, 1]

How should I use itertools.combinations to find all of the possible subsets of sums that there are with these integers. So that I get (an example of desired output with 3 integers - weight = [7, 5, 3]:

sums = [ [7], [7+5], [7+3], [7+5+3], [5], [5+3], [3] ]

Associated with these weights I have another array called luggages that is a list of lists with the luggage name and its correspondent weight in this format:

luggages = [["samsonite", 7], ["Berkin", 5], ["Catelli", 3] .....]

I created an array called weight in this manner.

weight = numpy.array([c[1] for c in luggages])

I could do this for the luggage names need be. I attempted to use itertools.combinations in this manner (upon suggestion):

comb = [combinations(weight, i) for i in range(len(luggages))]

My goal: To print out all the possible subsets of luggage names that I can bring on a trip given the max_weight = 23 kg of all the combination of each subset that satisfies the condition that the subsets sum equals EXACTLY 23 KG. In simpler terms I have to print out a list with the names of the luggages that if its weights were summed would equal the max_weight = 23 EXACTLY. Keed in mind: The luggages can be selected only once in each subset but they can appear in as many subsets as possible. Also, The number of items in each subset is irrelevant: it can be 1 luggage, 2, 3... as long as their sum equals exactly 23.

Upvotes: 4

Views: 2784

Answers (1)

BringMyCakeBack
BringMyCakeBack

Reputation: 1557

Working on the traveling salesman, are we? You can do this using everyone's favorite Python feature, list comprehensions:

weight = [7, 5, 3, 2, 9, 1]

cmb = []
for x in range(1, len(weight) + 1):
    cmb += itertools.combinations(weight, x)

#cmb now contains all combos, filter out ones over the limit

limit = 23

valid_combos = [i for i in cmb if sum(i) == limit]

print(valid_combos)

Upvotes: 5

Related Questions