17.4 variant 2: 3-sum problem

**lgtout** · November 24, 2017, 1:25am

[EPIJ 10/17 version]

Can the solution to 17.4 variant 2 perform better than O(k^(k-1)) time complexity (where k is the number of elements to sum)? Thanks!

**tsunghsienlee** · November 27, 2017, 6:25pm

Yes, I think you can easily solve this problem by O(k^ceil(k / 2)).

**lgtout** · December 4, 2017, 11:37pm

@tsunghsienlee
I have an idea that I think would achieve O(n^ceil(k/2)).
But you wrote O(k^ceil(k/2)), which has k as the base. Whereas I have n as the base.
Any chance you actually meant O(n^ceil(k/2)), not O(k^ceil(k/2))?

**tsunghsienlee** · December 4, 2017, 11:38pm

Sorry, it is a typo, definitely O(n^ceil(k/2)) as I was thinking. I was confused by your writing. You wrote O(k^ceil(k/2)).

**lgtout** · December 4, 2017, 11:44pm

Yes, you’re right. Thanks!

**laserrabbit** · August 13, 2019, 6:23am

Can you enlighten the idea please? I am trying to find the solution of this variant.