Subset sum with `itertools.combinations`
algorithm, python, recursion
Solution
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)
Problem
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.