> For the complete documentation index, see [llms.txt](https://r24zeng.gitbook.io/leetcode-notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://r24zeng.gitbook.io/leetcode-notebook/zhong-yu-shua-dao-100-dao-le-wo-shi-fen-shui-ling/bu-chong-120-dao/18.-4sum.md).

# 18. 4Sum

\# Medium

{% hint style="info" %}
Similar to **#15 3Sum** problem.

Two index(fixed) pointers(`i: 0 to len(nums)-3; j: i+1 to len(nums)-2`) and two flexible pointers(`z: j+1; k: len(nums)-1`). 

In order to avoid duplication, check duplicated number immediately after the two `for` loops.
{% endhint %}

{% tabs %}
{% tab title="Python" %}

```python
class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        # edge case
        if len(nums) < 4:
            return []
        
        # regular case
        result = set()
        nums2 = sorted(nums)
        for i in range(len(nums2)-3):
            if i > 0 and nums2[i] == nums2[i-1]:
                continue
            for j in range(i+1, len(nums2)-2):
                if j > i+1 and nums2[j] == nums2[j-1]:
                    continue
                z = j + 1
                k = len(nums2) - 1
                while z < k:
                    s = nums2[i] + nums2[j] + nums2[z] + nums2[k]
                    if s == target:
                        temp = (nums2[i], nums2[j], nums2[z], nums2[k])
                        result.add(temp)
                        z += 1
                        k -= 1
                    elif s > target:
                        k -= 1
                    else:
                        z += 1
        
        return result
```

{% endtab %}
{% endtabs %}

Time complexity = $$O(n^3)$$ , space complexity = $$O(1)$$ .

{% hint style="danger" %}
It can be extended to  kSum problem. Time complexity = $$O(n^{k-1})$$&#x20;
{% endhint %}