18. 4Sum

https://leetcode.com/problems/4sum/description/

input :

• nums, target

output :

• target을 만들 수 있는 모든 집합의 원소들을 반환하시오.

조건 :

• 1 <= nums.length <= 200

---

Solution explain : Solution1

idea

• 3Sum 문제의 idea와 같이 투 포인터를 사용함으로써 연산량을 줄여보자.
• nums를 우선 정렬한다.
• 4개의 원소로 이루어 지기 때문에 투 포인터를 2번 사용하는 방식을 사용하자.
• 재귀를 통해 (i + 1, l), (i, l - 1)의 순서로 줄어 들게 하자.
• 내부에선 j, k 인덱스를 +1, -1 하면서 업데이트 한다.
• val > target이면 k -= 1, val < target이면 k += 1
• set()을 사용하여 update(), union() 함수를 이용하여 합치자.

주의

• 재귀의 가장 큰 단점은 콜스택이 많이 쌓인다는 것이니 dp를 사용해서 이를 완화시키자.
• 반복문을 쓸 떄는 2번을 해야 한다(?) 할 수도 있으니 재귀를 하는게 차라리 낫지 않을까

from typing import List


class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        dp = dict()
        def recursive(i, l):
            if i + 2 >= l:
                return set()
            if (i, l) in dp:
                return dp[(i, l)]

            result = set()
            j, k = i + 1, l - 1
            while j < k:
                val = nums[i] + nums[k] + nums[l] + nums[j]
                if val == target:
                    result.add((nums[i], nums[j], nums[k], nums[l]))
                    j += 1
                    k -= 1
                elif val > target:
                    k -= 1
                else:
                    j += 1

            dp[(i + 1, l)] = recursive(i + 1, l)
            result.update(dp[(i + 1, l)])

            dp[(i, l - 1)] = recursive(i, l - 1)
            result.update(dp[(i, l - 1)])

            dp[(i, l)] = result
            return result

        nums.sort()
        ret = recursive(0, len(nums) - 1)
        return list(ret)


# s = Solution()
# print(s.fourSum([1, 0, -1, 0, -2, 2], 0))
# print(s.fourSum([2, 2, 2, 2, 2], 8))