Page **1** of **1**

### Re: 12911 - Subset sum

Posted: **Mon Jun 22, 2015 11:13 pm**

by **Repon kumar Roy**

Hi , I am using Meet In The Middle Technique for this Problem

Got AC

But Time > 2s ...

I see some other solution takes ~.1 sec..

What algorithm is needed to get such execution time ??

### Re: 12911 - Subset sum

Posted: **Tue Nov 17, 2015 5:20 pm**

by **Zyaad Jaunnoo**

What is the output for this input?

Code: Select all

```
40 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
```

On uDebug, the output is:

Shouldn't it be?

### Re: 12911 - Subset sum

Posted: **Wed Dec 30, 2015 7:36 pm**

by **dibery**

Zyaad Jaunnoo wrote:What is the output for this input?

Code: Select all

```
40 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
```

On uDebug, the output is:

Shouldn't it be?

Every element is considered different.

### Re: 12911 - Subset sum

Posted: **Wed Dec 30, 2015 7:54 pm**

by **dibery**

Repon kumar Roy wrote:Hi , I am using Meet In The Middle Technique for this Problem

Got AC

But Time > 2s ...

I see some other solution takes ~.1 sec..

What algorithm is needed to get such execution time ??

My solution ran about 0.113 sec.

You may refer to

https://en.wikipedia.org/wiki/Subset_sum_problem
Spoiler below:

I divide all numbers into 2 groups, and generate all possible subset sums of these 2 groups in ascending & decreasing order.

Each group has only 1M (2^20) subset sums at most.

Then, you can find the number of subsets whose sum equal to the target in linear time.

The only trick is to generate those 2 groups in order without calling sort().

### Re: 12911 - Subset sum

Posted: **Tue Jun 28, 2016 12:53 am**

by **tonybeeth**

dibery wrote:Repon kumar Roy wrote:Hi , I am using Meet In The Middle Technique for this Problem

Got AC

But Time > 2s ...

I see some other solution takes ~.1 sec..

What algorithm is needed to get such execution time ??

My solution ran about 0.113 sec.

You may refer to

https://en.wikipedia.org/wiki/Subset_sum_problem
Spoiler below:

I divide all numbers into 2 groups, and generate all possible subset sums of these 2 groups in ascending & decreasing order.

Each group has only 1M (2^20) subset sums at most.

Then, you can find the number of subsets whose sum equal to the target in linear time.

The only trick is to generate those 2 groups in order without calling sort().

Thanks for the hint. Can you explain how you can find the number of subsets whose sum equal the target in linear time. I understand it can be done in n^2 time but I can't figure the linear time method