# K Sum Problem Analysis: Recursive Implementation and Lower Bound

## Overview

I will give a recursive implementation for K sum, so any K Sum Problems (2sum, 3sum, 4sum, etc) could be solve by the same code in a consistent way, you just need to specify what K is. And the lower bound of the K sum problem is also given here just for your information, which is quite theoretical and research oriented.

Before this post, I have already talked about 2sum (post1post2post3),  3sum3sum closest4sum. In fact, all of them (expect 3sum closest) are just instances of a more general problem: K sum Problem. It is quite tempting to me at the first place to write a single piece of code to solve them all, which is what I did two years ago in this old post of mine and it is in Chinese. And quite many readers post their insightful comments and my thinking (copyright @sigmainfy) about K sum gets deeper and deeper, of course, some mistakes I have made are discovered too. So all of these just motivates me to start to write these series of 2sum, 3sum, 4sum, and K sum problem again to review, correct and record what I have in my mind,  and now all of them are in English so more readers could get to know and share my thinking and maybe comment too. I do hope these series of posts would bring the readers more fruitful results after the reading.

## K Sum Problem Definition:

So here we go the formal definition of the K sum Problem:

Given an array S of n integers, are there K elements (e.g., a, b, c, d, e … totally K elements) in S such that  their sum equal to a given target? Find all such unique K elements tuple(a, b, c, d, e, …) in the array which gives the given target.

Note:

• Elements in a tuple(a,b,c, d, e…) must be in non-descending order. (ie, a ≤ b ≤ c ≤ e…)
• The solution set must not contain duplicate triplets.

For example 1, given array S = {-1 0 1 2 -1 -4}, and K = 3 and target = 0

``````A solution set is:
(-1, 0, 1)
(-1, -1, 2)  For example 2, given array S = {1 0 -1 0 -2 2}, and K = 4 target = 0.

A solution set is:
(-1,  0, 0, 1)
(-2, -1, 1, 2)
(-2,  0, 0, 2)
``````

## K Sum Problem The Recursive Implementation:

If you have already read and implement the 3sum and 4sum by using the sorting approach: reduce them into 2sum at the end, you might already got the feeling that, the implementation for 4sum and 3sum got very similar patterns which is quite a good motivation for recursive implementation. So to tack K Sum problem in recursive way is just to reduce K sum problem to K – 1 sum Problem, and then to K – 2 Sum problem … Finally it would be reduced to the basic case 2sum problem. The ideas is simple and straightforward, the following is the source code and I test it for both 3sum and 4sum on leetcode OJ, this code could pass both of them:

For the time complexity, you could either use quite theoretical recursive formula to solve it or you just generalize from 4sum and 3sum, yes, you are right! It is O(N^(K-1)).

## K Sum Problem Lower Bound

Quite many people ask what is best we can do about K Sum Problem, I am not a theoretical guy but in research area, there are indeed quite a number of papers about (copyright @sigmainfy) the proof of the lower bound for K Sum Problem. As far as I know, Ω(n^ceil(k/2))  where ceil is the ceiling function is the most popular one, and I list all the resource as follows:

## Conclusion:

To summarize, I gave a recursive implementation for K sum here with the source code which could solve any K sum problems (2sum, 3sum, 4sum, .etc) . And the lower bound of the K sum problem Ω(n^ceil(k/2)) is also given with several useful links where you can find proof for that.

Written on September 23, 2014