Solution to hacker rank problem

solution.py

# A businessman dealing in salt goes to do business in a country named "strangeland" . The pricing of commodities in this country is quite strange indeed. Here salt is sold only in quantised packets which are multiple of 1 kilogram. The pricing is such that for a packet of i kilogram , the price is p[i] silver coins. The businessman has N kilogram of salt to sell. He wants your help to pack it so that he can earn maximum profit in "strangeland".

# Input Format
# First line of the input file contains a single integer T, the number of test cases.
# Every test case starts with a line containing the integer N , total amount of salt.
# The next line contains N space separated integers where the i-th integer is P[i] , the price of a salt packet of i Kilogram.



#int partition function
def get_combi(n):
    c = []
    c.append([()])
    c.append([(1,)])
    for num in range(2, n+1):
        pt = set()
        for i in range(num):
            for t in c[i]:
                pt.add(tuple(sorted((num - i, ) + t)))
        c.append(list(pt))
    return c[n]


test = int(input())

for _ in range(test):
    N = int(input())
    P = list(map(int, input().split()))
    cost = []
    A = get_combi(N)
    #getting combunation of numbers
    for i in A:
        #calculating cost by storing sum of number of  i'th P in a list cost
        cost.append(sum([P[s-1] for s in i]))    
    print(max(cost))   #printing max profit.
    
    
#output 
# 2
# 4
# 27211 31805 24769 12123
# 108844
# 3
# 6559 29531 22159
# 36090