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 ??
12911  Subset sum
Moderator: Board moderators

 Learning poster
 Posts: 96
 Joined: Tue Apr 23, 2013 12:54 pm

 Experienced poster
 Posts: 122
 Joined: Tue Apr 16, 2002 10:07 am
Re: 12911  Subset sum
What is the output for this input?
On uDebug, the output is:
Shouldn't it be?
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
Code: Select all
1099511627775
Code: Select all
40
Re: 12911  Subset sum
Every element is considered different.Zyaad Jaunnoo wrote:What is the output for this input?On uDebug, the output is: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
Shouldn't it be?Code: Select all
1099511627775
Code: Select all
40
Life shouldn't be null.
Re: 12911  Subset sum
My solution ran about 0.113 sec.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 ??
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.
Re: 12911  Subset sum
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 methoddibery wrote:My solution ran about 0.113 sec.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 ??
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().