# Summary for LeetCode 2Sum, 3Sum, 4Sum, K Sum

## Overview

I summarize various solutions (sort, hash, etc) for the leetcode 2Sum, 3Sum, 4Sum problems as well as how to optimize and some important remarks. An elegant recursive implementation and the lower bound for the more general K sum problem is given too.

## K Sum Problem Series

Originally, I summarize leetcode 2Sum, 3Sum, 4Sum, K Sum in Chinese below the red line which got quite a lot of discussion. So I decide to rewrite another series of K sum problem analysis in English with the insightful comments below integrated, some sophisticated  issues resolved and some mistakes corrected. I hope these English versions of K sum problems could be more specific and concrete, and hopefully, those posts could give us more fruitful results and would be more helpful to more people (so those who cannot read Chinese could now read them). Of course, if you can read Chinese, the following one below the red line is also a good one for your reference! :)

• 2Sum: Discuss the basic stuff including the sort and hash method, duplicates issues are raised up and discussed, Index Pair VS Value Pair are distinguished. Should be a good tutorial for beginners to explore K sum problem
• 3Sum: An old issue bothered me for quite a while about how to remove duplicates triplets in the results without using std:set is addressed and an extension for 3sum closest problem is given too
• 4Sum: Normal sorting approach reduced to 3sum and then 2sum is given and an even faster approach based on hash is discussed
• K Sum: generalize the 2sum, 3sum, 4sum problems into K sum, and the source code of recursive implementation is given which I consider quite elegant. Lower bound and related papers of proof for K sum is discussed too

## LeetCode All Problem Solution Index:

And I have summarized the solutions to all LeetCode problems by organizing them into closely related categories (Backtracking, Greedy, DP, Search, Sum, Tree, Linked List, Array, Simulation, Math, Hash, Bit Operation and Others) and give tree index page for quick references. You might want to check them too.

################### Below is the Old Chinese Version ###################

### leetcode求和问题描述(K sum problem)：

K sum的求和问题一般是这样子描述的：给你一组N个数字(比如 vector num), 然后给你一个常数(比如 int target) ，我们的goal是在这一堆数里面找到K个数字，使得这K个数字的和等于target。

### K Sum求解方法, 适用leetcode 2Sum, 3Sum, 4Sum：

2sum的算法复杂度是O(N log N) 因为排序用了N log N以及头尾指针的搜索是线性的，所以总体是O(N log N)，好了现在考虑3sum, 有了2sum其实3sum就不难了，这样想：先取出一个数，那么我只要在剩下的数字里面找到两个数字使得他们的和等于(target – 那个取出的数)就可以了吧。所以3sum就退化成了2sum, 取出一个数字，这样的数字有N个，所以3sum的算法复杂度就是O(N^2 ), 注意这里复杂度是N平方，因为你排序只需要排一次，后面的工作都是取出一个数字，然后找剩下的两个数字，找两个数字是2sum用头尾指针线性扫，这里很容易错误的将复杂度算成O(N^2 log N)，这个是不对的。我们继续的话4sum也就可以退化成3sum问题(copyright @sigmainfy)，那么以此类推，K-sum一步一步退化，最后也就是解决一个2sum的问题，K sum的复杂度是O(n^(K-1))。 这个界好像是最好的界了，也就是K-sum问题最好也就能做到O(n^(K-1))复杂度，之前有看到过有人说可以严格数学证明，这里就不深入研究了。

### 4sum的hash算法：

O(N^2)把所有pair存入hash表，并且每个hash值下面可以跟一个list做成map， map[hashvalue] = list，每个list中的元素就是一个pair, 这个pair的和就是这个hash值，那么接下来求4sum就变成了在所有的pair value中求 2sum，这个就成了线性算法了，注意这里的线性又是针对pair数量(N^2)的线性，所以整体上这个算法是O(N^2)，而且因为我们挂了list, 所以只要符合4sum的我们都可以找到对应的是哪四个数字。

## Summary

To summarize, various solutions for the leetcode 2Sum, 3Sum, 4Sum problems as well as how to optimize and some important remarks are given. An elegant recursive implementation and the lower bound for the more general K sum problem is given too.

Written on January 8, 2013