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:

vector< vector<int> > KSum(vector<int> &num, int K, int target, int p) {
		vector< vector<int> > vecResults;
		if (K == 2) { // base case
			vector<int> tuple(2, 0);
			int i = p, j = num.size() - 1;
			while (i < j) {
				if (i > p && num[i] == num[i - 1]) {
					++i;
					continue;
				}
				int sum = num[i] + num[j];
				if (sum == target) {
					tuple[0] = num[i++];
					tuple[1] = num[j--];
					vecResults.push_back(tuple);
				}
				else if (sum > target) {
					--j;
				}
				else {
					++i;
				}
			}
			return vecResults;
		}
		// K > 2
		for (int i = p; i < num.size(); ++i) {
			if (i > p && num[i] == num[i - 1]) continue;
			vector< vector<int> > K1Sum = KSum(num, K - 1, target - num[i], i + 1);
			for (auto it = K1Sum.begin(); it != K1Sum.end(); ++it) {
				vector<int> tuple;
				tuple.push_back(num[i]);
				tuple.insert(tuple.end(), it->begin(), it->end());
				vecResults.push_back(tuple);
			}
		}
		return vecResults;
	}

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