There is a set of N integers in range [-1000, 1000], N< 1000

I have to find if there is any subset which sum of elements is exactly S.

S is an integer in range [-1 000 000, 1 000 000 ]

Example:

Set - {5, 10, 25, 50}

S = 30

I can find a subset {5,25} - 5+25 = 30

Set - { -6,9,100,-45}

S = -42

I can find a subset {-6,9,-45} - (-6)+9+(-45) = 3 + (-45) = (-42)

Set - {-5, 10, 20, 100}

Set = 3

I can't find any set which sum is exacly 3.

Please help

## Problem with sum of seqence

**Moderator:** Board moderators

Yours advice bad cose S very big {TLE I think}Artikali wrote:http://www.comp.nus.edu.sg/~stevenha/pr ... ing_Change

Anyway I think the constraints are not high enough to preclude using the dp solution (of course this depends on the time limit, but I don't think anyone knows a better approach).

I've finally solve this problem.

I've created two arrays:

bool wasadd[2 000 001]

and

int sums[2 000 001]

It's "only" 2 000 000 possible sums.

I show my algorithm using example:

Set: 2,3,4 Sum to find: 7

wassadd[2+1 000 000] = 1;

sums[0] = 2;

Code: Select all

```
for members of set from 3 to 4 do
for every integer in sums array:
if (wassad[sums[x]+actual member of set+ 1 000 000]==0)
add sums[x]+actual member to sums array
wassad[sums[x]+actual member of set+ 1 000 000]=1
if (wassad[sumtofind + 1 000 000]==1) i can find sum in this set
```

Fristly

wassad: 1 000 002 are "1"

sums: 2

Actual member of set - 3

wassad: 1 000 002, 1 000 003, 1 000 005 are "1"

sums: 2, 3, 5

Aktual member of set - 4

wassad: 1 000 002, 1 000 003, 1 000 005, 1 000 004, 1 000 006, 1 000 007, , 1 000 009 are "1"

sums: 2, 3, 5, 4, 6, 7, 9

1 000 007 is "1" so I can find subset which sum is 7

I hope you understand