MAIN72 - Subset sum

You are given an array of N integers. Now you want to find the sum of all those integers which can be expressed as the sum of at least one subset of the given array.

Input

First line contains T the number of test case. then T test cases follow, first line of each test case contains N (1 <= N <= 100) the number of integers, next line contains N integers, each of them is between 0 and 1000 (inclusive).  

Output

For each test case print the answer in a new line.

Example

Input:
2
2
0 1
3
2 3 2

Output:
1
21

Added by:Mahesh Chandra Sharma
Date:2011-03-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem used for NSIT-IIITA main contest #7

hide comments
2014-08-13 19:57:37 S
@chayan:O(Maxsum*n) using dp :)
2011-04-03 06:10:16 Santiago Palacio
@sushant thank you very much! i didn't saw the problem properly!
2011-04-01 15:00:09 sushant bhatia
@Santiago: We do not have to find the sum of all the subsets. We need to find the sum of all the numbers that can be represented as a subset. In this case only numbers 0 and 1 can be represented. So the sum = 0 + 1 = 1
2011-04-01 07:38:13 Santiago Palacio
Why is the fisrst test case 1? isnt it (0,1) + (1) + (0) which will be 2???
2011-03-26 16:36:01 chayan ghosh
will brute force lead to TLE? plz tell me if there exists a polynomial time algorithm
2011-03-18 12:17:06 :D
You completely didn't understand this problem.
The subsets are: {}, {2a},{3},{2b},{2a,3},{2a,2b},{3,2b},{2a,3,2b}.
That gives sums: 0,2,3,2,5,4,5,7.
Distinct sums are: 0,2,3,4,5,7.
2011-03-18 07:53:43 Amit Jain
i think for above second case,answer must be 11
take {2,3,2} as {2a,3,2b}
{2a},{3},{2b},{2b}(for 2a),{2a}(for 2b)

if i'm wrong please correct me.....
Edit: How are you getting 11? and btw did you considered all possible 8 subsets?

Amit:i understood finding the sum of those element of array which can be represented by sum of any subset of elements of given array

Last edit: 2011-03-18 17:45:36
2011-03-15 17:07:32 zetro
what the output if N=3
and N=7???
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.