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.


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).  


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


0 1
2 3 2


hide comments
loser_404: 2021-01-03 07:47:42

AC in one go.

Last edit: 2022-06-16 17:16:40
robosapien: 2020-09-10 23:16:38

dp: 0.03s
bitset: 0.00s

lakshya1st: 2020-08-28 15:58:25

AC in one go!! Simple recursive DP implementation of subset sum

vidit1400: 2020-05-05 19:24:49

If going for recursive solu treat dp as visited array ie 1 if visited and -1 if not .

Last edit: 2020-05-05 19:25:10
auler_: 2020-04-07 15:55:45

Subset sum problem!

dkkv0000: 2020-01-21 11:05:32

wow topdown(dp+unordered_set)

pratiyush_05: 2019-08-05 15:15:42

My first dp problem.....accepted ...yeah

Last edit: 2019-08-05 15:16:03
sky_scraper: 2019-06-05 09:30:44

Iterative - set/unordered set -> AC
Even if you like recursive solution try the iterative one and vice versa.

Last edit: 2019-06-05 09:31:55
abhinav_kr: 2019-05-22 20:01:04

Unordered_set + Memoization + fast I/O : AC 0.06s

demon8778: 2018-11-22 08:59:19

Guys!! Need help here. I have solved this problem but it took me about 4 hours. can anyone please help how do I improve my speed for solving problems?

Added by:Mahesh Chandra Sharma
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