12911 - Subset sum

All about problems in Volume 129. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

Re: 12911 - Subset sum

Post by Repon kumar Roy » Mon Jun 22, 2015 11:13 pm

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 ??

User avatar
Zyaad Jaunnoo
Experienced poster
Posts: 120
Joined: Tue Apr 16, 2002 10:07 am

Re: 12911 - Subset sum

Post by Zyaad Jaunnoo » Tue Nov 17, 2015 5:20 pm

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:

Code: Select all

1099511627775
Shouldn't it be?

Code: Select all

40

dibery
Learning poster
Posts: 75
Joined: Sat Feb 23, 2013 4:16 pm
Location: Taiwan, Taipei
Contact:

Re: 12911 - Subset sum

Post by dibery » Wed Dec 30, 2015 7:36 pm

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:

Code: Select all

1099511627775
Shouldn't it be?

Code: Select all

40
Every element is considered different.
Life shouldn't be null.

dibery
Learning poster
Posts: 75
Joined: Sat Feb 23, 2013 4:16 pm
Location: Taiwan, Taipei
Contact:

Re: 12911 - Subset sum

Post by dibery » Wed Dec 30, 2015 7:54 pm

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().
Life shouldn't be null.

tonybeeth
New poster
Posts: 2
Joined: Mon Mar 14, 2016 10:11 pm

Re: 12911 - Subset sum

Post by tonybeeth » Tue Jun 28, 2016 12:53 am

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

Post Reply

Return to “Volume 129 (12900-12999)”

Who is online

Users browsing this forum: No registered users and 1 guest