TCS Codevita : Hotel trip

roblem : Hotel trip

Tom, Dick and Harry go to a restaurant. Each of them has a certain amount of money. When their monies are pooled they discover they have S Rs. Next, they start going through the menu card to choose items they would like to order.

Your task is to help them find out how many different menu item combinations they can order. Since there can be many menu items with the same price, we are interested only in unique price combinations. Refer output specifications and examples to get a better understanding. 

Input Format:

First line contains N positive integers delimited by space, corresponding to prices of N menu items
Second line contains an integer S corresponding to the amount of money pooled between them 

Output Format: 

1.    Print all possible combinations of item prices whose sum is equal to S. Enclose each such combination in square brackets [ ]. Elements should be separated by, followed by a space character.

2.    Item price combinations must be unique (See example 2 to understand this better)

3.    If more than one combinations exists, then the print order should be as follows 

a.     Combinations should be printed in descending order item prices

b.    Two combinations can be differentiated by first comparing their costliest, followed by second costliest, and followed by the next costliest item, so on and so forth. Refer example outputs for better understanding of print order.

Constraints:

P_i > 0 ; where i = 1 to N and Pi denotes the price of the i^th item

S > 0

Sample Input and Output

SNo.	Input	Output
1	10 7 6 5 3 2 1 23	[10, 7, 6] [10, 7, 5, 1] [10, 7, 3, 2, 1] [10, 6, 5, 2] [7, 6, 5, 3, 2]
2	50 100 1 1 1 1 1 51	[50, 1]
3	50 100 4 3 1 1 1 1 54	[50, 4] [50, 3, 1] [50, 1, 1, 1, 1]

Explanation:

In example 1 there are 7 items on the menu each having a fixed price. Tom, Dick and Harry have 23 Rs/- amongst them. So they can order the following combinations 

1. [10, 7, 6]
2. [10, 7, 5, 1]
3. [10, 7, 3, 2, 1]
4. [10, 6, 5, 2]
5. [7, 6, 5, 3, 2]

Note how the items are sorted in descending order within a combination. Also note how the combinations themselves are too sorted in descending order.

In example 2 there are 7 items. 5 of these 7 items have the same price. Tom, Dick and Harry have 51 Rs/- amongst them. So the only unique price combination they can order is [50, 1]

In example 3 there are 8 items. 4 of these 8 items have the same price. Tom, Dick and Harry have 54 Rs/- amongst them. So they can form the following combinations. 

1. [50, 4]
2. [50, 3, 1]
3. [50, 1, 1, 1, 1]

Again, note how the items are sorted in descending order within a combination. Also note how the combinations themselves are too sorted in descending order. Also combinations 2 and 3 are printed only once. 

Solution in Python :

tt = input().split()

pm = int(input())

comb = list()

for ind in range(0,len(tt)):

tt[ind] = int(tt[ind])

def subset_sum(numbers, target, partial=[]):

    s = sum(partial)

    if s == target:

        comb.append(partial)

    if s >= target:

        return

    for ind in range(len(numbers)):

        n = numbers[ind]

        remaining = numbers[ind+1:]

        subset_sum(remaining, target, partial + [n])

subset_sum(tt,pm)

unique = []

for item in comb:

    if sorted(item) not in unique:unique.append(sorted(item))

for items in unique:

    print(items[::-1])