[Leetcode] 18. 4 sum

[Problem Link] : https://leetcode.com/problems/4sum/

[Difficulty] : Medium

[Problem Description]

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

[Problem Explanation]

這題是非常經典的four sum題，要求出在給定的一數組中，任何四個數字加總符合target的解總共有幾組，其中每組解不得重複。

[Think Process]

這題如果有做過“3-sum”，應該是不難，主要挑這題出來整理是為了把“K-Sum”題目做一個總結，並且給一個通解來解決“K-Sum”問題。

2-Sum

2-Sum解法簡單，基本上就是使用hashtable來紀錄出現的數字，然後遍歷nums，在nums[i]搜尋hashtable是否有target-nums[i]，若有則輸出答案，這個解法的時間複雜度為O(n)。

3-Sum

Get Yi-Ting Lin’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

3-Sum第一個解法其實也是多一個for(j from 0 to n)迴圈，然後依序呼叫2-Sum這樣解法的時間複雜度為O(n²)，不過需要使用hashtable。不過其實有另一個解法可以直接省掉hashtable，並且時間複雜度同樣為O(n²)，首先我們針對nums做排序，在排序之後我們同樣使用一個for迴圈(i from 0 to n)，裡面再用兩個指針l & r分別代表nums[i]與nums.back()，而這三個index所代表的數字可以形成以下三種狀況：

1. nums[i] + nums[l] + nums[r] > target：這代表我們總和太小，因此在有排序過的nums數組裡面，在i已經用for迴圈遍歷的情況下，我們需要把比較小的數字nums[l]向右移(l=l+1)以增加總和。
2. nums[i] + nums[l] + nums[r] < target：同上，這次我們要將較大的數字nums[r]向左移(r=r-1)。
3. nums[i] + nums[l] + nums[r] =target：儲存結果，並且因為已經輸出該結果，故兩個指標皆須移動(l=l+1, r=r-1)。

4-Sum or K-Sum

同3-Sum的想法，第一個解就是再加上一個for迴圈，而其實k-sum都可以依此類推，但因為不知道k到底需要幾個for迴圈，因此通解用遞迴表示。

[Solution#1] Combined by 3-Sum

PS1. 在k-Sum的題目裡面，都需要注意去除重複解的問題，其中一個偷吃步的方法是使用STL::set，它可以直接幫忙除去重複的解，不過正統的解法還是去看下一個數是否一樣來去除重複的數字。

[Solution#2] General solution for K-Sum

PS1. 通解的去除重複數組較難理解，不過要注意的是因為邊界從[0:size-1]變成了[l:r]所以需要注意與原本的for迴圈版本不同，真的不行就用for迴圈或者set實作吧。

PS2. 移動指針的判斷式也比較難理解，不過概念上就是在兩個指針裡面，若取k個的最大值(nMin +(k-1)*nMax)還是小於target的前提下，就代表需要把最小值往左移，而另一個情況也類似。

PS3. 這邊我們使用了遞回來取代for迴圈，故一個遞迴以後都要將l+1。

[Complexity Analysis]

General Solution for K-sum with numbers in size N:

Time complexity：O(N^(K-1))，因為總共會從K一路遞迴至2，每一層遞迴的時間複雜度為O(N)。

Space complexity：O(K-1)，遞迴深度為K-1，基本上可以視為O(1)。