# 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 (post1, post2, post3), 3sum, 3sum closest, 4sum. 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:

- Lower Bounds for Linear Degeneracy Testing : this paper just proves the lower bound of Ω(n^ceil(k/2)) for K sum equal to zero
- “generalised-3sum-k-sum-problem“: here in this link, the UIUC professor Jeff Erickson answered this question and he has his own paper discuss the lower bound too
- Someone in the leetcode forum point it out that there exist better
**quantum**algorithms. The quantum complexity of k-SUM is Θ(n^(k/(k+1)) which is sub-linear! And there are two papers about this bound: ”Quantum walk algorithm for element“, “Adversary Lower Bound for the k-sum Problem“

## 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.