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
hide comments
|
S:
2014-08-13 19:57:37
@chayan:O(Maxsum*n) using dp :) |
|
Santiago Palacio:
2011-04-03 06:10:16
@sushant thank you very much! i didn't saw the problem properly! |
|
sushant bhatia:
2011-04-01 15:00:09
@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 |
|
|
Santiago Palacio:
2011-04-01 07:38:13
Why is the fisrst test case 1? isnt it (0,1) + (1) + (0) which will be 2??? |
|
chayan ghosh:
2011-03-26 16:36:01
will brute force lead to TLE? plz tell me if there exists a polynomial time algorithm |
|
:D:
2011-03-18 12:17:06
You completely didn't understand this problem.
|
|
Amit Jain:
2011-03-18 07:53:43
i think for above second case,answer must be 11
|
|
zetro:
2011-03-15 17:07:32
what the output if N=3
|
| 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 |
RSS