Given an array of integers and another number. Find all the unique quadruple from the given array that sums up to the given number.
Example 1:
Input:
N = 5, K = 3
A[] = {0,0,2,1,1}
Output: 0 0 1 2 
Explanation: Sum of 0, 0, 1, 2 is equal
to K.
Example 2:
Input:
N = 7, K = 23
A[] = {10,2,3,4,5,7,8}
Output: 2 3 8 10 
        2 4 7 10 
        3 5 7 8 
Explanation: Sum of 2, 3, 8, 10 = 23,
sum of 2, 4, 7, 10 = 23 and sum of 3,
5, 7, 8 = 23.
Your Task:
You don't need to read input or print anything. Your task is to complete the function fourSum() which takes the array arr[] and the integer k as its input and returns an array containing all the quadruples in a lexicographical manner. Also note that all the quadruples should be internally sorted, ie for any quadruple [q1, q2, q3, q4] the following should follow: q1 <= q2 <= q3 <= q4.  (In the output each quadruple is separate by $. The printing is done by the driver's code)
Expected Time Complexity: O(N^{3}).
Expected Auxiliary Space: O(N^{2}).
Constraints:
1 <= N <= 100
-1000 <= K <= 1000
-100 <= A[] <= 100

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Sorting

Data structures

Starter code: #User function Template for python3



# arr[] : int input array of integers

# k : the quadruple sum required

class Solution:

    def fourSum(self, arr, k):

        # code here

Solutions:
class Solution:

	def fourSum(self, arr, k):
		arr.sort()
		target = k
		ans = set()
		for i in range(len(arr) - 3):
			for j in range(i + 1, len(arr) - 2):
				k = j + 1
				l = len(arr) - 1
				while k < l:
					sum = arr[i] + arr[j] + arr[k] + arr[l]
					if sum == target:
						ans.add((arr[i], arr[j], arr[k], arr[l]))
						k += 1
					if sum < target:
						k += 1
					else:
						l -= 1
		return sorted(ans)


class Solution:

	def fourSum(self, arr, k):
		n = len(arr)
		arr.sort()
		quadruples = []
		for i in range(n - 3):
			if i > 0 and arr[i] == arr[i - 1]:
				continue
			for j in range(i + 1, n - 2):
				if j > i + 1 and arr[j] == arr[j - 1]:
					continue
				left = j + 1
				right = n - 1
				while left < right:
					current_sum = arr[i] + arr[j] + arr[left] + arr[right]
					if current_sum == k:
						quadruples.append([arr[i], arr[j], arr[left], arr[right]])
						while left < right and arr[left] == arr[left + 1]:
							left += 1
						while left < right and arr[right] == arr[right - 1]:
							right -= 1
						left += 1
						right -= 1
					elif current_sum < k:
						left += 1
					else:
						right -= 1
		return quadruples


class Solution:

	def fourSum(self, arr, k):
		l = set()
		arr.sort()
		for i in range(n - 3):
			for j in range(i + 1, n - 2):
				left = j + 1
				right = n - 1
				while left < right:
					four = arr[i] + arr[j] + arr[left] + arr[right]
					if four == k:
						l.add((arr[i], arr[j], arr[left], arr[right]))
						left += 1
					elif four < k:
						left += 1
					else:
						right -= 1
		l = sorted(list(l))
		return l


class Solution:

	def fourSum(self, arr, k):
		arr.sort()
		ans = set()
		for i in range(n - 3):
			for j in range(i + 1, n - 2):
				left = j + 1
				right = n - 1
				while left < right:
					summ = arr[i] + arr[j] + arr[left] + arr[right]
					if summ == k:
						ans.add((arr[i], arr[j], arr[left], arr[right]))
						left += 1
					elif summ > k:
						right -= 1
					else:
						left += 1
		ans = sorted(ans)
		return ans


class Solution:

	def fourSum(self, arr, k):
		if len(arr) < 4:
			return -1
		arr.sort()
		check = set()
		for i in range(0, n - 3):
			for j in range(i + 1, n - 2):
				left = j + 1
				right = n - 1
				while left < right:
					ssum = arr[i] + arr[j] + arr[left] + arr[right]
					if ssum > k:
						right -= 1
					elif ssum == k:
						temp = (arr[i], arr[j], arr[left], arr[right])
						check.add(temp)
						left += 1
					else:
						left += 1
		return sorted(list(check))


class Solution:

	def solve(self, idx, arr, k, N, path, ans):
		try:
			if N == 0:
				if sum(path) == k:
					temp = tuple(path[:])
					ans.add(temp)
				return
			if idx >= len(arr):
				return
			path.append(arr[idx])
			self.solve(idx + 1, arr, k, N - 1, path, ans)
			path.pop()
			self.solve(idx + 1, arr, k, N, path, ans)
		except Exception as e:
			print(e)

	def solve(self, idx, arr, k, N, path, ans):
		try:
			if N == 0:
				if sum(path) == k:
					temp = tuple(path[:])
					ans.add(temp)
				return
			if idx >= len(arr):
				return
			for i in range(idx, len(arr)):
				path.append(arr[i])
				self.solve(i + 1, arr, k, N - 1, path, ans)
				path.pop()
		except Exception as e:
			print(e)

	def solve(self, arr, k, ans):
		n = len(arr)
		for i in range(n - 3):
			for j in range(i + 1, n - 2):
				left = j + 1
				right = n - 1
				while left < right:
					summ = arr[i] + arr[j] + arr[left] + arr[right]
					if summ == k:
						ans.add((arr[i], arr[j], arr[left], arr[right]))
						left += 1
					elif summ > k:
						right -= 1
					else:
						left += 1

	def fourSum(self, arr, k):
		arr.sort()
		ans = set()
		self.solve(arr, k, ans)
		ans = sorted(ans)
		return ans


class Solution:

	def fourSum(self, arr, k):
		arr.sort()
		res = []
		for i in range(len(arr) - 3):
			if i > 0 and arr[i] == arr[i - 1]:
				continue
			for j in range(i + 1, len(arr) - 2):
				if j > i + 1 and arr[j] == arr[j - 1]:
					continue
				l = j + 1
				r = len(arr) - 1
				while l < r:
					if arr[i] + arr[j] + arr[l] + arr[r] == k:
						res.append((arr[i], arr[j], arr[l], arr[r]))
						while l < r and arr[l] == arr[l + 1]:
							l += 1
						while l < r and arr[r] == arr[r - 1]:
							r -= 1
						l += 1
						r -= 1
					elif arr[i] + arr[j] + arr[l] + arr[r] > k:
						r -= 1
					else:
						l += 1
		return res


class Solution:

	def fourSum(self, arr, k):
		arr = sorted(arr)
		d = dict()
		n = len(arr)
		for i in range(n - 3):
			for j in range(i + 1, n - 2):
				l = j + 1
				r = n - 1
				while l < r:
					tmp = arr[i] + arr[j] + arr[l] + arr[r]
					if tmp == k:
						val = tuple([arr[i], arr[j], arr[l], arr[r]])
						if val not in d:
							d[val] = 1
						else:
							d[val] += 1
						l += 1
					elif tmp > k:
						r -= 1
					else:
						l += 1
		return sorted(list(d.keys()))


class Solution:

	def fourSum(self, arr, k):
		d = dict()
		arr = sorted(arr)
		n = len(arr)
		for i in range(n - 3):
			for j in range(i + 1, n - 2):
				left = j + 1
				right = n - 1
				while left < right:
					temp = arr[i] + arr[j] + arr[left] + arr[right]
					if temp == k:
						key = tuple([arr[i], arr[j], arr[left], arr[right]])
						if key not in d:
							d[key] = 1
						else:
							d[key] += 1
						left += 1
						right -= 1
					elif temp < k:
						left += 1
					else:
						right -= 1
		return sorted(list(d.keys()))


class Solution:

	def fourSum(self, arr, k):
		list1 = set()
		arr.sort()
		for i in range(n - 3):
			for j in range(i + 1, n - 2):
				left = j + 1
				right = n - 1
				while left < right:
					quad = arr[i] + arr[j] + arr[left] + arr[right]
					if quad == k:
						temp = (arr[i], arr[j], arr[left], arr[right])
						list1.add(temp)
						left += 1
					elif quad > k:
						right -= 1
					else:
						left += 1
		return sorted(list(list1))


def findFourSum(arr, i, n, curSum, x, l, ans):
	if i == n:
		if l == 4 and sum(curSum) == x:
			ans.append(curSum.copy())
			curSum = []
		return ans
	if l == 4:
		if sum(curSum) == x:
			ans.append(curSum.copy())
			curSum = []
		return ans
	curSum.append(arr[i])
	ans = findFourSum(arr, i + 1, n, curSum, x, l + 1, ans)
	curSum.remove(arr[i])
	ans = findFourSum(arr, i + 1, n, curSum, x, l, ans)
	return ans

class Solution:

	def fourSum(self, arr, k):
		arr.sort()
		i = 0
		n = len(arr)
		res = []
		while i < n:
			j = i + 1
			while j < n:
				l = j + 1
				r = n - 1
				s = arr[i] + arr[j]
				while l < r:
					if s + arr[l] + arr[r] == k:
						res.append([arr[i], arr[j], arr[l], arr[r]])
						l += 1
						while l < r and arr[l - 1] == arr[l]:
							l += 1
						r -= 1
						while l < r and arr[r + 1] == arr[r]:
							r -= 1
					elif s + arr[l] + arr[r] < k:
						l += 1
						while l < r and arr[l - 1] == arr[l]:
							l += 1
					else:
						r -= 1
						while l < r and arr[r + 1] == arr[r]:
							r -= 1
				j += 1
				while j < n and arr[j - 1] == arr[j]:
					j += 1
			i += 1
			while i < n and arr[i - 1] == arr[i]:
				i += 1
		return res


class Solution:

	def fourSum(self, arr, k):
		arr.sort()
		ans = []
		for i in range(len(arr)):
			if i > 0 and arr[i] == arr[i - 1]:
				continue
			for j in range(i + 1, len(arr)):
				if j > i + 1 and arr[j] == arr[j - 1]:
					continue
				(l, r) = (j + 1, len(arr) - 1)
				while l < r:
					s = arr[i] + arr[j] + arr[l] + arr[r]
					if s == k:
						ans.append([arr[i], arr[j], arr[l], arr[r]])
						while l < r and arr[l] == arr[l + 1]:
							l += 1
						while l < r and arr[r] == arr[r - 1]:
							r -= 1
						l += 1
						r -= 1
					elif s > k:
						r -= 1
					else:
						l += 1
		return ans


class Solution:

	def fourSum(self, nums, target):
		output = []
		nums.sort()
		for i in range(len(nums)):
			if i > 0 and nums[i] == nums[i - 1]:
				continue
			for j in range(i + 1, len(nums)):
				if j > i + 1 and nums[j] == nums[j - 1]:
					continue
				(third, fourth) = (j + 1, len(nums) - 1)
				while third < fourth:
					s = nums[i] + nums[j] + nums[third] + nums[fourth]
					if s > target:
						fourth -= 1
					elif s < target:
						third += 1
					else:
						output.append([nums[i], nums[j], nums[third], nums[fourth]])
						while third < fourth and nums[third] == nums[third + 1]:
							third += 1
						while third < fourth and nums[fourth] == nums[fourth - 1]:
							fourth -= 1
						third += 1
						fourth -= 1
		return output


class Solution:

	def fourSum(self, arr, k):
		arr.sort()
		res = []
		for i in range(len(arr) - 3):
			if i != 0 and arr[i] == arr[i - 1]:
				continue
			for j in range(i + 1, len(arr) - 2):
				if j != i + 1 and arr[j] == arr[j - 1]:
					continue
				sumij = arr[i] + arr[j]
				low = j + 1
				high = len(arr) - 1
				while low < high:
					sumval = sumij + arr[low] + arr[high]
					if sumval == k:
						res.append([arr[i], arr[j], arr[low], arr[high]])
						low += 1
						high -= 1
						while low < high and arr[low] == arr[low - 1]:
							low += 1
						while low < high and arr[high] == arr[high + 1]:
							high -= 1
					elif sumval > k:
						high -= 1
					else:
						low += 1
		return res


class Solution:

	def fourSum(self, arr, k):
		res = []
		arr.sort()
		if len(arr) == 0:
			return []
		n = len(arr)
		for i in range(n):
			if i > 0 and arr[i] == arr[i - 1]:
				continue
			for j in range(i + 1, n):
				if j > i + 1 and arr[j] == arr[j - 1]:
					continue
				target = k - (arr[i] + arr[j])
				left = j + 1
				right = n - 1
				while left < right:
					targetsum = arr[left] + arr[right]
					if targetsum < target:
						left += 1
					elif targetsum > target:
						right -= 1
					else:
						quad = [arr[i], arr[j], arr[left], arr[right]]
						res.append(quad)
						while left < right and arr[left] == quad[2]:
							left += 1
						while left < right and arr[right] == quad[3]:
							right -= 1
		return res


class Solution:

	def fourSum(self, arr, k):
		ml = []
		k1 = {}
		s = 0
		c = 0
		arr = sorted(arr)
		for i in range(len(arr)):
			for j in range(i + 1, len(arr)):
				l = j + 1
				h = len(arr) - 1
				while l < h:
					s = arr[i] + arr[j] + arr[l] + arr[h]
					if s < k:
						l = l + 1
					elif s > k:
						h = h - 1
					else:
						c = c + 1
						k1[arr[i], arr[j], arr[l], arr[h]] = c
						x = arr[l]
						y = arr[h]
						while l < h and x == arr[l]:
							l = l + 1
						while l < h and y == arr[h]:
							h = h - 1
		myKeys = list(k1.keys())
		myKeys.sort()
		return myKeys


class Solution:

	def fourSum(self, arr, k):
		temparr = []
		arr.sort()
		for i in range(n - 2):
			sum1 = k - arr[i]
			for j in range(i + 1, n - 1):
				sum2 = sum1 - arr[j]
				mapp = {}
				for l in range(j + 1, n):
					if sum2 - arr[l] in mapp:
						temparr.append((arr[i], arr[j], sum2 - arr[l], arr[l]))
					else:
						mapp[arr[l]] = 1
		x = list(set(temparr))
		x.sort()
		return x


class Solution:

	def fourSum(self, A, k):
		A.sort()
		n = len(A)
		res = []
		for i in range(n - 3):
			if i > 0 and A[i] == A[i - 1]:
				continue
			for j in range(i + 1, n - 2):
				if j > i + 1 and A[j] == A[j - 1]:
					continue
				(p, q) = (j + 1, n - 1)
				while p < q:
					s = A[i] + A[j] + A[p] + A[q]
					if s == k:
						res.append([A[i], A[j], A[p], A[q]])
					if s < k:
						p += 1
						while p < q and A[p] == A[p - 1]:
							p += 1
					else:
						q -= 1
						while p < q and A[q] == A[q + 1]:
							q -= 1
		return res


class Solution:

	def fourSum(self, arr, k):
		arr.sort()
		n = len(arr)
		res = []
		for i in range(n - 2):
			for j in range(i + 1, n - 1):
				l = j + 1
				r = n - 1
				while l < r:
					summ = arr[i] + arr[j] + arr[l] + arr[r]
					if summ == k:
						li = []
						li.append(arr[i])
						li.append(arr[j])
						li.append(arr[l])
						li.append(arr[r])
						res.append(li)
						l += 1
						r -= 1
					elif summ < k:
						l += 1
					else:
						r -= 1
		setList = list(set(map(tuple, res)))
		setList.sort()
		return setList


class Solution:

	def fourSum(self, A, X):
		A.sort()
		N = len(A)
		arr = []
		for i in range(N - 3):
			if i > 0 and A[i] == A[i - 1]:
				continue
			for j in range(i + 1, N - 2):
				if j > i + 1 and A[j] == A[j - 1]:
					continue
				k = j + 1
				l = n - 1
				while k < l:
					sum1 = A[i] + A[j] + A[k] + A[l]
					if sum1 == X:
						ind = [A[i], A[j], A[k], A[l]]
						arr.append(ind)
						k += 1
						l -= 1
						while k < l and k > j and (A[k] == A[k - 1]):
							k += 1
						while k < l and l + 1 < N and (A[l] == A[l + 1]):
							l -= 1
					elif sum1 < X:
						k += 1
					else:
						l -= 1
		return arr


class Solution:

	def fourSum(self, arr, target):
		arr.sort()
		n = len(arr)
		pair_sum = {}
		for i in range(n - 1):
			for j in range(i + 1, n):
				s = arr[i] + arr[j]
				if s not in pair_sum:
					pair_sum[s] = [(i, j)]
				else:
					pair_sum[s].append((i, j))
		result = set()
		for i in range(n - 3):
			if i > 0 and arr[i] == arr[i - 1]:
				continue
			for j in range(i + 1, n - 2):
				if j > i + 1 and arr[j] == arr[j - 1]:
					continue
				s = arr[i] + arr[j]
				if target - s in pair_sum:
					pairs = pair_sum[target - s]
					for p in pairs:
						if p[0] > j:
							result.add((arr[i], arr[j], arr[p[0]], arr[p[1]]))
		result = sorted(result)
		return result


class Solution:

	def fourSum(self, arr, k):
		arr.sort()
		res = []
		for i in range(0, len(arr) - 3):
			for j in range(i + 1, len(arr) - 2):
				l = j + 1
				h = len(arr) - 1
				while l < h:
					s = arr[i] + arr[j] + arr[l] + arr[h]
					if s == k:
						temp = []
						temp.append(arr[i])
						temp.append(arr[j])
						temp.append(arr[l])
						temp.append(arr[h])
						res.append(temp)
					if s < k:
						l = l + 1
					else:
						h = h - 1
		set_list = list(set(map(tuple, res)))
		set_list.sort()
		return set_list


class Solution:

	def fourSum(self, arr, k):
		arr.sort()
		a = []
		for i in range(0, len(arr) - 3):
			for j in range(i + 1, len(arr) - 2):
				s = k - (arr[i] + arr[j])
				start = j + 1
				end = len(arr) - 1
				while start < end:
					t = arr[start] + arr[end]
					if t == s:
						l = []
						l.append(arr[i])
						l.append(arr[j])
						l.append(arr[start])
						l.append(arr[end])
						a.append(l)
						start += 1
						end -= 1
					elif t > s:
						end -= 1
					else:
						start += 1
		set_list = list(set(map(tuple, a)))
		set_list.sort()
		return set_list


class Solution:

	def fourSum(self, arr, k):
		arr.sort()
		Len = len(arr)
		Ans = []
		for First in range(Len - 3):
			if First > 0 and arr[First] == arr[First - 1]:
				continue
			for Second in range(First + 1, Len - 2):
				if Second > First + 1 and arr[Second] == arr[Second - 1]:
					continue
				Left = Second + 1
				Right = Len - 1
				while Left < Right:
					temp = arr[First] + arr[Second] + arr[Left] + arr[Right]
					if temp == k:
						Ans += [[arr[First], arr[Second], arr[Left], arr[Right]]]
					if temp > k:
						Right -= 1
						while Left < Right and arr[Right] == arr[Right + 1]:
							Right -= 1
					else:
						Left += 1
						while Left < Right and arr[Left] == arr[Left - 1]:
							Left += 1
		return Ans


class Solution:

	def fourSum(self, nums, target):
		n = len(nums)
		nums.sort()
		ans = []
		for i in range(n):
			if i > 0 and nums[i] == nums[i - 1]:
				continue
			for j in range(i + 1, n):
				if j != i + 1 and nums[j] == nums[j - 1]:
					continue
				k = j + 1
				l = n - 1
				while k < l:
					sum = nums[i]
					sum += nums[j]
					sum += nums[k]
					sum += nums[l]
					if sum == target:
						ans.append([nums[i], nums[j], nums[k], nums[l]])
						k += 1
						l -= 1
						while k < l and nums[k] == nums[k - 1]:
							k += 1
						while k < l and nums[l] == nums[l + 1]:
							l -= 1
					elif sum < target:
						k += 1
					else:
						l -= 1
		return ans


class Solution:

	def fourSum(self, arr, k):
		n = len(arr)
		ans = []
		arr.sort()
		for i in range(n - 2):
			x1 = k - arr[i]
			for j in range(i + 1, n - 1):
				x2 = x1 - arr[j]
				res = {}
				for ii in range(j + 1, n):
					if x2 - arr[ii] in res:
						N = x2 - arr[ii]
						ans.append((arr[i], arr[j], N, arr[ii]))
					else:
						res[arr[ii]] = 1
		y = list(set(ans))
		y.sort()
		return y


class Solution:

	def fourSum(self, arr, k):
		ans = []
		arr.sort()
		n = len(arr)
		for i in range(n):
			if i == 0 or (i > 0 and arr[i] != arr[i - 1]):
				for j in range(i + 1, n):
					if j == i + 1 or (j > i + 1 and arr[j] != arr[j - 1]):
						l = j + 1
						m = n - 1
						while l < m:
							sum = arr[i] + arr[j] + arr[l] + arr[m]
							if sum == k:
								temp = [arr[i], arr[j], arr[l], arr[m]]
								ans.append(temp)
								while l < m and arr[l] == arr[l + 1]:
									l += 1
								while l < m and arr[m] == arr[m - 1]:
									m -= 1
								l += 1
								m -= 1
							elif sum < k:
								l += 1
							else:
								m -= 1
		return ans


class Solution:

	def fourSum(self, nums, target):
		nums.sort()
		arr = []
		quad = []

		def kSum(k, start, target):
			if k != 2:
				for i in range(start, len(nums) - k + 1):
					if i > start and nums[i] == nums[i - 1]:
						continue
					quad.append(nums[i])
					kSum(k - 1, i + 1, target - nums[i])
					quad.pop()
				return
			l = start
			r = len(nums) - 1
			while l < r:
				if nums[l] + nums[r] < target:
					l += 1
				elif nums[l] + nums[r] > target:
					r -= 1
				else:
					t = quad + [nums[l], nums[r]]
					arr.append(t)
					l += 1
					while nums[l] == nums[l - 1] and l < r:
						l += 1
		kSum(4, 0, target)
		return arr


class Solution:

	def fourSum(self, arr, k):
		arr.sort()
		res = []
		for i in range(len(arr) - 3):
			for j in range(i + 1, len(arr) - 2):
				x = j + 1
				y = len(arr) - 1
				while x < y:
					s = arr[i] + arr[j] + arr[x] + arr[y]
					if s == k:
						res.append([arr[i], arr[j], arr[x], arr[y]])
					if s < k:
						x += 1
					else:
						y -= 1
		set_list = list(set(map(tuple, res)))
		set_list.sort()
		return set_list


class Solution:

	def fourSum(self, arr, k):
		n = len(arr)
		res = []
		arr.sort()
		for i in range(n - 2):
			A = k - arr[i]
			for j in range(i + 1, n - 1):
				B = A - arr[j]
				ans = {}
				for ij in range(j + 1, n):
					if B - arr[ij] in ans:
						N = B - arr[ij]
						res.append((arr[i], arr[j], N, arr[ij]))
					else:
						ans[arr[ij]] = 1
		C = list(set(res))
		C.sort()
		return C


class Solution:

	def fourSum(self, arr, k):
		target = k
		arr.sort()
		ans = []
		n = len(arr)
		for i in range(n):
			if i > 0 and arr[i] == arr[i - 1]:
				continue
			for j in range(i + 1, n):
				if j > i + 1 and arr[j] == arr[j - 1]:
					continue
				(o, l) = (j + 1, n - 1)
				while o < l:
					sum1 = arr[i] + arr[j] + arr[o] + arr[l]
					if sum1 > target:
						l -= 1
					elif sum1 < target:
						o += 1
					else:
						ans.append([arr[i], arr[j], arr[o], arr[l]])
						o += 1
						l -= 1
						while o < l and arr[o] == arr[o - 1]:
							o += 1
						while k < l and arr[l] == arr[l + 1]:
							l -= 1
		return ans


class Solution:

	def fourSum(self, arr, k):
		li = []
		n = len(arr)
		if n < 4:
			return li
		arr.sort()
		for i in range(n - 3):
			if arr[i] > 0 and arr[i] > k:
				break
			if i > 0 and arr[i] == arr[i - 1]:
				continue
			for j in range(i + 1, n - 2):
				if j > i + 1 and arr[j] == arr[j - 1]:
					continue
				l = j + 1
				r = n - 1
				while l < r:
					old_l = l
					old_r = r
					s = arr[i] + arr[j] + arr[l] + arr[r]
					if s == k:
						p = []
						p.append(arr[i])
						p.append(arr[j])
						p.append(arr[l])
						p.append(arr[r])
						li.append(p)
						while l < r and arr[old_l] == arr[l]:
							l += 1
						while l < r and arr[r] == arr[old_r]:
							r = r - 1
					elif s < k:
						l = l + 1
					else:
						r = r - 1
		return li


class Solution:

	def fourSum(self, arr, k):
		arr.sort()
		result = set()
		for i in range(len(arr)):
			r = []
			for j in range(i + 1, len(arr)):
				sum1 = arr[i] + arr[j]
				diff = k - sum1
				m = j + 1
				l = len(arr) - 1
				while m < l:
					remaining_sum = arr[m] + arr[l]
					if remaining_sum > diff:
						l -= 1
					elif remaining_sum < diff:
						m += 1
					else:
						r.append(arr[i])
						r.append(arr[j])
						r.append(arr[m])
						r.append(arr[l])
						result.add((arr[i], arr[j], arr[m], arr[l]))
						m += 1
						l -= 1
		return sorted(result)


class Solution:

	def fourSum(self, arr, k):
		arr.sort()
		n = len(arr)
		r = []
		for i in range(0, len(arr) - 3):
			for j in range(i + 1, len(arr) - 2):
				l = j + 1
				m = len(arr) - 1
				while l < m:
					s = arr[i] + arr[j] + arr[l] + arr[m]
					if s == k:
						x = [arr[i], arr[j], arr[l], arr[m]]
						x.sort()
						r.append(x)
					if s > k:
						m -= 1
					else:
						l += 1
		set_list = list(set(map(tuple, r)))
		set_list.sort()
		return set_list


class Solution:

	def fourSum(self, arr, k):
		arr.sort()
		li = set()
		summ = 0
		for i in range(n - 3):
			for j in range(i + 1, n - 2):
				l = j + 1
				h = n - 1
				while l < h:
					summ = arr[i] + arr[j] + arr[l] + arr[h]
					if summ == k:
						li.add((arr[i], arr[j], arr[l], arr[h]))
						l += 1
						h -= 1
					elif summ < k:
						l += 1
					else:
						h -= 1
		return sorted(li)


class Solution:

	def fourSum(self, arr, target):
		arr.sort()
		n = len(arr)
		res = []
		for i in range(n - 3):
			if i > 0 and arr[i] == arr[i - 1]:
				continue
			for j in range(i + 1, n - 2):
				if j > i + 1 and arr[j] == arr[j - 1]:
					continue
				s = j + 1
				e = n - 1
				while s < e:
					if s > j + 1 and arr[s] == arr[s - 1]:
						s += 1
						continue
					if e + 1 < n and arr[e] == arr[e + 1]:
						e -= 1
						continue
					tmp = arr[i] + arr[j] + arr[s] + arr[e]
					if tmp == target:
						tmpArr = [arr[i], arr[j], arr[s], arr[e]]
						res.append(tmpArr)
						s += 1
					elif tmp > target:
						e -= 1
					else:
						s += 1
		return res


class Solution:

	def fourSum(self, arr, k):
		n = len(arr)
		ans_set = set()
		arr.sort()
		for i in range(n - 3):
			for j in range(i + 1, n - 2):
				l = j + 1
				r = n - 1
				while l < r:
					sum = arr[i] + arr[j] + arr[l] + arr[r]
					if sum == k:
						ans_set.add((arr[i], arr[j], arr[l], arr[r]))
						l += 1
						r -= 1
					elif sum < k:
						l += 1
					else:
						r -= 1
		ans_list = list(ans_set)
		ans_list.sort()
		return ans_list


class Solution:

	def fourSum(self, arr, k):
		n = len(arr)
		ans = []
		arr.sort()
		for i in range(n - 3):
			if i == 0 or (i > 0 and arr[i] != arr[i - 1]):
				for j in range(i + 1, n - 2):
					if j == i + 1 or (j > i + 1 and arr[j] != arr[j - 1]):
						left = j + 1
						right = n - 1
						while left < right:
							Sum = arr[i] + arr[j] + arr[left] + arr[right]
							if Sum == k:
								ans.append((arr[i], arr[j], arr[left], arr[right]))
								while left < right and arr[left] == arr[left + 1]:
									left += 1
								while left < right and arr[right] == arr[right - 1]:
									right -= 1
								left += 1
								right -= 1
							elif Sum < k:
								left += 1
							else:
								right -= 1
		return ans


class Solution:

	def fourSum(self, a, k):
		n = len(a)
		ans = []
		if n < 4:
			return ans
		a.sort()
		for i in range(0, n - 3):
			if a[i] > 0 and a[i] > k:
				break
			if i > 0 and a[i] == a[i - 1]:
				continue
			for j in range(i + 1, n - 2):
				if j > i + 1 and a[j] == a[j - 1]:
					continue
				left = j + 1
				right = n - 1
				while left < right:
					old_l = left
					old_r = right
					sum = a[i] + a[j] + a[left] + a[right]
					if sum == k:
						ans.append([a[i], a[j], a[left], a[right]])
						while left < right and a[left] == a[old_l]:
							left += 1
						while left < right and a[right] == a[old_r]:
							right -= 1
					elif sum > k:
						right -= 1
					else:
						left += 1
		return ans


class Solution:

	def fourSum(self, arr, k):
		n = len(arr)
		ans = []
		arr.sort()
		for i in range(n - 3):
			for j in range(i + 1, n - 2):
				left = j + 1
				right = n - 1
				while left < right:
					curr_sum = arr[i] + arr[j] + arr[left] + arr[right]
					if curr_sum == k:
						ans.append((arr[i], arr[j], arr[left], arr[right]))
						left += 1
						right -= 1
					elif curr_sum < k:
						left += 1
					else:
						right -= 1
		ans = list(set(ans))
		ans.sort()
		return ans


class Solution:

	def fourSum(self, arr, k):
		ty = []
		arr.sort()
		for i in range(n - 2):
			a = k - arr[i]
			for j in range(i + 1, n - 1):
				b = a - arr[j]
				mapp = {}
				for l in range(j + 1, n):
					if b - arr[l] in mapp:
						ty.append((arr[i], arr[j], b - arr[l], arr[l]))
					else:
						mapp[arr[l]] = 1
		x = list(set(ty))
		x.sort()
		return x


class Solution:

	def fourSum(self, arr, k):
		arr.sort()
		(res, quad) = ([], [])
		length = len(arr)

		def nSum(n, start, k):
			if n != 2:
				for i in range(start, length - n + 1):
					if i > start and arr[i] == arr[i - 1]:
						continue
					quad.append(arr[i])
					nSum(n - 1, i + 1, k - arr[i])
					quad.pop()
				return
			(l, r) = (start, length - 1)
			while l < r:
				if arr[l] + arr[r] > k:
					r -= 1
				elif arr[l] + arr[r] < k:
					l += 1
				else:
					res.append(quad + [arr[l], arr[r]])
					l += 1
					while arr[l] == arr[l - 1] and l < r:
						l += 1
		nSum(4, 0, k)
		return res


class Solution:

	def fourSum(self, nums, k):
		ans = []
		n = len(nums)
		if not nums or n == 0:
			return []
		nums.sort()
		i = 0
		while i < n:
			j = i + 1
			while j < n:
				twoSumTarget = k - nums[i] - nums[j]
				left = j + 1
				right = n - 1
				while left < right:
					current = nums[left] + nums[right]
					if current < twoSumTarget:
						left += 1
					elif current > twoSumTarget:
						right -= 1
					else:
						quad = [nums[i], nums[j], nums[left], nums[right]]
						ans.append(quad)
						while left < right and nums[left] == quad[2]:
							left += 1
						while left < right and nums[right] == quad[3]:
							right -= 1
				while j + 1 < n and nums[j + 1] == nums[j]:
					j += 1
				j += 1
			while i + 1 < n and nums[i + 1] == nums[i]:
				i += 1
			i += 1
		return ans


class Solution:

	def fourSum(self, arr, k):
		arr.sort()
		n = len(arr)
		ans = []
		for i in range(n - 3):
			for j in range(i + 1, n - 2):
				l = j + 1
				r = n - 1
				while l < r:
					s = arr[i] + arr[j] + arr[l] + arr[r]
					if s == k:
						ans += [[arr[i], arr[j], arr[l], arr[r]]]
						l += 1
						r -= 1
					elif s < k:
						l += 1
					else:
						r -= 1
		set_list = list(set(map(tuple, ans)))
		set_list.sort()
		return set_list


class Solution:

	def fourSum(self, arr, k):
		arr.sort()
		n = len(arr)
		lst = []
		for i in range(n - 3):
			for j in range(i + 1, n - 2):
				(l, r) = (j + 1, n - 1)
				while l < r:
					sum4 = arr[i] + arr[j] + arr[l] + arr[r]
					if sum4 > k:
						r -= 1
					elif sum4 < k:
						l += 1
					elif sum4 == k:
						lst.append([arr[i], arr[j], arr[l], arr[r]])
						l += 1
						r -= 1
		lst = list(set(map(tuple, lst)))
		lst.sort()
		return lst


from collections import Counter

class Solution:

	def fourSum(self, arr, k):
		dic = Counter(arr)
		ansset = set()
		ans = []
		arr.sort()
		n = len(arr)
		for i in range(n):
			for j in range(i + 1, n):
				for l in range(j + 1, n):
					temp = k - arr[i] - arr[j] - arr[l]
					if temp >= arr[l] and temp in dic:
						ftemp = dic[temp]
						count = 1
						for x in (arr[i], arr[j], arr[l]):
							if x == temp:
								count += 1
						if ftemp - count >= 0:
							if (arr[i], arr[j], arr[l], temp) not in ansset:
								ans.append((arr[i], arr[j], arr[l], temp))
								ansset.add((arr[i], arr[j], arr[l], temp))
		return ans


class Solution:

	def fourSum(self, arr, d):
		res = []
		arr.sort()
		for i in range(n - 3):
			for j in range(i + 1, n - 2):
				(k, l) = (j + 1, n - 1)
				while k < l:
					s = arr[i] + arr[j] + arr[k] + arr[l]
					if s == d:
						res.append([arr[i], arr[j], arr[k], arr[l]])
						k += 1
						l -= 1
					elif s < d:
						k += 1
					else:
						l -= 1
		r = list(set(map(tuple, res)))
		r.sort()
		return r


class Solution:

	def fourSum(self, nums, target):
		result = []
		nums.sort()
		for i in range(len(nums) - 3):
			if i > 0 and nums[i] == nums[i - 1]:
				continue
			for j in range(i + 1, len(nums) - 2):
				if j > i + 1 and nums[j] == nums[j - 1]:
					continue
				sum = target - nums[i] - nums[j]
				l = j + 1
				r = len(nums) - 1
				while l < r:
					if nums[l] + nums[r] == sum:
						result.append([nums[i], nums[j], nums[l], nums[r]])
						while l < r and nums[l] == nums[l + 1]:
							l += 1
						while l < r and nums[r] == nums[r - 1]:
							r -= 1
						l += 1
						r -= 1
					elif nums[l] + nums[r] < sum:
						l += 1
					else:
						r -= 1
		return result


class Solution:

	def fourSum(self, nums, target):
		res = []
		if not nums or len(nums) < 4:
			return res
		nums.sort()
		n = len(nums)
		for i in range(n - 3):
			if i > 0 and nums[i] == nums[i - 1]:
				continue
			for j in range(i + 1, n - 2):
				if j > i + 1 and nums[j] == nums[j - 1]:
					continue
				left = j + 1
				right = n - 1
				while left < right:
					total = nums[i] + nums[j] + nums[left] + nums[right]
					if total == target:
						res.append([nums[i], nums[j], nums[left], nums[right]])
						while left < right and nums[left] == nums[left + 1]:
							left += 1
						while left < right and nums[right] == nums[right - 1]:
							right -= 1
						left += 1
						right -= 1
					elif total < target:
						left += 1
					else:
						right -= 1
		return res


class Solution:

	def fourSum(self, arr, k):
		n = len(arr)
		arr.sort()
		ans = set()
		op = []
		for i in range(n):
			sum3 = k - arr[i]
			for j in range(i + 1, n):
				sum2 = sum3 - arr[j]
				left = j + 1
				right = n - 1
				while right > left:
					if arr[left] + arr[right] > sum2:
						right -= 1
					elif arr[left] + arr[right] < sum2:
						left += 1
					else:
						ans.add((arr[i], arr[j], arr[left], arr[right]))
						left += 1
						right -= 1
		op = list(ans)
		op.sort()
		return op


class Solution:

	def fourSum(self, arr, k):
		arr.sort()
		x = set()
		ans = []
		for i in range(len(arr) - 3):
			for j in range(i + 1, len(arr) - 2):
				left = j + 1
				right = len(arr) - 1
				while left < right:
					cur = arr[left] + arr[right] + arr[i] + arr[j]
					if cur > k:
						right -= 1
					elif cur < k:
						left += 1
					else:
						s = ''
						s += str(arr[i]) + '.'
						s += str(arr[j]) + '.'
						s += str(arr[left]) + '.'
						s += str(arr[right]) + '.'
						if s not in x:
							t = [arr[i], arr[j], arr[left], arr[right]]
							ans.append(t)
							x.add(s)
						left += 1
		return ans


class Solution:

	def fourSum(self, arr, k):
		n = len(arr)
		res = set()
		arr.sort()
		for i in range(n - 3):
			for j in range(i + 1, n - 2):
				left = j + 1
				right = n - 1
				while left < right:
					s = arr[i] + arr[j] + arr[left] + arr[right]
					if s == k:
						res.add((arr[i], arr[j], arr[left], arr[right]))
						left += 1
						right -= 1
					elif s < k:
						left += 1
					else:
						right -= 1
		return sorted(list(res))