K sum problem

Dec. 29, 2017

Introduction

I spend time to get organized last 5 practice of Leetcode 18 4 sum algorithm. And then I came cross a blog written 18 months ago, and then started to read the blog.

The blog is title called "K sum problem". It is written in Chinese and the link is here.

K sum problem 

The mock interview practice is to relate to how to quickly figure out the solution and also write code in less than 30 minutes, sometimes it should take less than 20 minutes, or less than 10 minutes. The training is to focus on good understanding of the algorithm, not too much theory involved.

But I do have strong interest in the topic about time complexity. So I decide to copy and paste the Chinese writing here, and modify the content in terms of style, make it more readable. But the time I spent on is over 30 minutes now. I decide to find a good written article in English instead.

Later on do some study related to it.

k sum problem （k 个数的求和问题）

问题陈述：

在一个数组，从中找出 k 个数（每个数不能重复取。数组中同一个值有多个，可以取多个），使得和为零。
找出所有这样的组合，要求没有重复项（只要值不同即可，不要求在原数组中的 index 不同）

解法：

2 sum 用 hash table 做，可以时间 O(n)，空间 O(n).
2 sum 如果用 sort 以后，在前后扫描，可以时间O(nlogn + n) = O(nlogn)，空间O(1)
2 sum 用 hash table 做的好处是快，但是等于是利用了不用排序的特点。排序的办法，在高维度（也就是k sum问题，k>2) 的时候，nlogn 就不是主要的时间消耗成分，也就更适合 2 sum 的 sort 后双指针扫描查找的办法。

那么，对于 k sum， k > 2 的，如果用sort的话，可以 对 n - 2 的数做嵌套循环，因为已经sort过了，最后剩下的两维用2 sum的第二个办法， 时间是O(nlogn + n^(k-2) * n) = O(n^(n-1))，空间O(1)。 但是这样跟纯嵌套循环没有什么区别，只是最后一层少了一个因子n。有什么办法能优化？
就是说，对于 k sum (k > 2) 问题 （一个size为 n 的array, 查找 k 个数的一个tuple，满足总和 sum 为0）， 有没有时间复杂度在O(n^(k-2))的办法？

之前常规的一层一层剥离，n 的次数是递增的。只有在最后一层，还有两个维度的时候，时间开销上减少一个 n 的因子，但是这样时间开销还是太多

我们可以通过对问题分解来解决
举个例子 [..., -5，-4，-3，-2，-1, 0，1, 2, 3, 4, 5, ...] 要找 4 sum = 0. 那么先分解 4 分成 2 sum + 2 sum 来解决，但是这里的子问题 2 sum 没有sum = 0 的要求，是保留任何中间值。只有当子问题的 2 sum 解决以后，回归原问题的时候，我们才又回归原始的 2 sum 问题，这时候 sum = 0
子问题，空间和时间消耗，都是 O(n²). 回归大问题，时间消耗，是O(n²).

假设 k sum 中  k = 2^m, 那么一共有 m 层，会有 m 次分解
分解到最底层，时间空间消耗 从 原始 O(n) 变为新的 O(n²).
分解到次底层，时间空间消耗 从 O(n²) 变为新的 O((n²)²)
...
到达最顶层，时间空间消耗就都变成了O(n^(2*m)) = O(n^(2logk))

和之前的方法 O(n^(k-1)) 相比，O(n^(2logk)) 的时间是少了很多，但是空间消耗却很大。
因为子问题无法确定把哪一个中间结果留下，那么就需要把子问题的结果全部返回，到最后，空间消耗就很大了。整体效果算是空间换时间吧。

通过 问题的分解 + hashtable 的运用，能明显减少时间消耗, 但是空间消耗变大是个问题。比如说，如果有10⁶的 int 类型数组，我如果用这个hashtable的办法，就要有10¹²的pair，这就有 10T 以上的空间消耗。

问题的分解是个很好的思路，但是中间值得保留迫使空间消耗增大，这和用不用hashtable倒没有很大关系，只是说，如果不用hashtable，时间消耗会更大。

另外，还有一些题目的变形，比如如果要求所有组合，满足
sum < k,
sum = k,
sum > k,
或者是 closest to k
遇到这些变形的时候，hashtable 的做法就显得乏力了，但是嵌套循环的方式却仍是可行的。尤其是对closest to k 这种非确定性的要求。