Given an array A of N integers. You have to find whether a combination of four elements in the array whose sum is equal to a given value X exists or not.
 
Example 1:
Input:
N = 6
A[] = {1, 5, 1, 0, 6, 0}
X = 7
Output:
1
Explantion:
1, 5, 1, 0 are the four elements which makes sum 7.
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function find4Numbers() which takes the array A[], its size N and an integer X as inputs and returns true if combination is found else false. Driver code will print 1 or 0 accordingly.
 
Expected Time Complexity: O(N^{3})
Expected Auxiliary Space: O(1)
 
Constraints:
4 <= N <= 100
1 <= A[i] <= 1000

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Amortized analysis

Starter code: #User function Template for python3

def find4Numbers( A, n, X):
    # return true or false
    



Solutions:
def find4Numbers(A, n, X):
	A.sort()
	for i in range(n - 3):
		for j in range(i + 1, n - 2):
			left = j + 1
			right = n - 1
			while left < right:
				current_sum = A[i] + A[j] + A[left] + A[right]
				if current_sum == X:
					return True
				elif current_sum < X:
					left += 1
				else:
					right -= 1
	return False


def find4Numbers(A, n, X):
	A.sort()
	for i in range(n - 3):
		s = 0
		for j in range(i + 1, n - 2):
			s = X - A[i] - A[j]
			th = j + 1
			fo = n - 1
			while th < fo:
				su = A[th] + A[fo]
				if su < s:
					th += 1
				elif su > s:
					fo -= 1
				else:
					return True
	return False


def find4Numbers(A, n, X):
	A.sort()
	for i in range(n):
		for j in range(i + 1, n):
			summ = A[i] + A[j]
			if summ > X:
				break
			summ = X - summ
			l = j + 1
			r = n - 1
			while l < r:
				if A[l] + A[r] == summ:
					return True
				elif A[l] + A[r] < summ:
					l += 1
				else:
					r -= 1
	return False


def find4Numbers(A, n, X):
	for i in range(n - 3):
		for j in range(i + 1, n):
			for k in range(j + 1, n):
				if X - (A[i] + A[j] + A[k]) in A[k + 1:n]:
					return True
	return False


def find4Numbers(A, n, X):
	A.sort()
	for i in range(n):
		for j in range(i + 1, n):
			s = j + 1
			e = n - 1
			while s < e:
				sum = A[i] + A[j] + A[s] + A[e]
				if sum == X:
					return True
				elif sum > X:
					e -= 1
				else:
					s += 1
	return False


def find4Numbers(lst, n, X):
	lst.sort()
	for i in range(n - 3):
		for j in range(i + 1, n - 2):
			p = j + 1
			q = n - 1
			while p < q:
				if lst[i] + lst[j] + lst[p] + lst[q] == X:
					return True
				elif lst[i] + lst[j] + lst[p] + lst[q] > X:
					q -= 1
				else:
					p += 1
	return False


def find4Numbers(A, n, X):
	A.sort()
	for i in range(n):
		for j in range(i + 1, n):
			(st, en) = (j + 1, n - 1)
			while st < en:
				temp = A[i] + A[j] + A[st] + A[en]
				if temp > X:
					en -= 1
				elif temp < X:
					st += 1
				else:
					return True
	return False


def find4Numbers(arr, n, x):
	arr.sort()
	s = 0
	for i in range(n - 3):
		for j in range(i + 1, n - 2):
			l = j + 1
			h = n - 1
			while l < h:
				s = arr[i] + arr[j] + arr[l] + arr[h]
				if s == x:
					return True
				elif s < x:
					l += 1
				else:
					h -= 1
	return False


def find4Numbers(A, n, X):
	A.sort()
	for i in range(len(A) - 3):
		for j in range(i + 1, len(A) - 2):
			k = j + 1
			l = len(A) - 1
			while k < l:
				four_sum = A[i] + A[j] + A[k] + A[l]
				if four_sum == X:
					return True
				elif four_sum < X:
					k += 1
				else:
					l -= 1
	return False


def find4Numbers(A, n, X):
	A.sort()
	for i in range(0, n - 3):
		for j in range(i + 1, n - 2):
			pos1 = j + 1
			pos2 = n - 1
			while pos2 > pos1:
				if A[i] + A[j] + A[pos1] + A[pos2] == X:
					return True
				elif A[i] + A[j] + A[pos1] + A[pos2] > X:
					pos2 -= 1
				else:
					pos1 += 1
	return False


def find4Numbers(A, n, X):
	A.sort()
	for i in range(n - 3):
		for j in range(i + 1, n - 2):
			l = j + 1
			r = n - 1
			while l < r:
				curr_sum = A[i] + A[j] + A[l] + A[r]
				if curr_sum == X:
					return True
				elif curr_sum < X:
					l += 1
				else:
					r -= 1
	return False


def find4Numbers(A, n, X):
	A.sort()
	for i in range(0, n - 2):
		for j in range(i + 1, n - 1):
			l = j + 1
			r = n - 1
			while l < r:
				sum = A[i] + A[j] + A[l] + A[r]
				if sum == X:
					return True
				elif sum < X:
					l += 1
				else:
					r -= 1
	return False


from itertools import combinations

def find4Numbers(A, n, X):
	a = combinations(A, 4)
	for i in a:
		(x, y, x1, y1) = i
		if x + y + x1 + y1 == X:
			return 1
	else:
		return 0


def find4Numbers(A, n, X):
	A.sort()
	for i in range(n - 3):
		for j in range(i + 1, n - 2):
			low = j + 1
			high = n - 1
			while low < high:
				if A[i] + A[low] + A[high] + A[j] == X:
					return True
				elif A[i] + A[low] + A[high] + A[j] < X:
					low = low + 1
				else:
					high = high - 1
	return False


def find4Numbers(A, n, X):
	A.sort()
	for p1 in range(n - 3):
		for p2 in range(p1 + 1, n - 2):
			p3 = p2 + 1
			p4 = n - 1
			while p3 < p4:
				if A[p1] + A[p2] + A[p3] + A[p4] == X:
					return True
				elif A[p1] + A[p2] + A[p3] + A[p4] > X:
					p4 -= 1
				else:
					p3 += 1
	return False


def find4Numbers(arr, n, x):
	arr.sort()
	i = 0
	while i < n:
		j = i + 1
		while j < n:
			k = j + 1
			m = n - 1
			while k < m:
				a = arr[i] + arr[j] + arr[k] + arr[m]
				if a == x:
					return True
				elif a < x:
					k += 1
				else:
					m -= 1
			j += 1
		i += 1
	return False


def find4Numbers(arr, n, X):
	arr.sort()
	for i in range(n - 3):
		for j in range(i + 1, n - 2):
			k = j + 1
			l = n - 1
			while k < l:
				res = arr[i] + arr[j] + arr[k] + arr[l]
				if res == X:
					return 1
				elif res < X:
					k += 1
				else:
					l -= 1
	return 0


def find4Numbers(A, n, X):
	A.sort()
	for i in range(n - 3):
		for j in range(i + 1, n - 2):
			k = j + 1
			l = n - 1
			while k < l:
				s = A[i] + A[j] + A[k] + A[l]
				if s == X:
					return True
				if s < X:
					k += 1
				else:
					l -= 1
	return False


def find4Numbers(A, n, X):
	t = {}
	for i in A:
		if i in t:
			t[i] += 1
		else:
			t[i] = 1
	A.sort()
	for i in range(n - 3):
		for j in range(i + 1, n - 2):
			for k in range(j + 1, n - 1):
				s = A[i] + A[j] + A[k]
				d = X - s
				if d in t:
					c = [A[i], A[j], A[k]].count(d)
					if t[d] >= c + 1:
						return True
				if s > X:
					break
	return False


def find4Numbers(A, n, X):

	def fun(A, X):
		A.sort()
		count = 0
		for i in range(len(A)):
			for j in range(i + 1, len(A)):
				l = j + 1
				m = len(A) - 1
				while l < m:
					sumi = A[i] + A[j] + A[l] + A[m]
					if sumi > X:
						m = m - 1
					elif sumi < X:
						l = l + 1
					elif sumi == X:
						return True
		return count
	return fun(A, X)


def find4Numbers(arr, n, X):
	arr.sort()
	for i in range(n - 3):
		for j in range(i + 1, n - 2):
			k = j + 1
			p = n - 1
			while k < p:
				if arr[i] + arr[j] + arr[k] + arr[p] > X:
					p -= 1
				elif arr[i] + arr[j] + arr[k] + arr[p] < X:
					k += 1
				else:
					return [arr[i], arr[j], arr[k], arr[p]]


def find4Numbers(A, n, X):
	A.sort()
	count = 0
	for i in range(n - 3):
		for j in range(i + 1, n - 2):
			l = j + 1
			r = n - 1
			while l < r:
				s = A[i] + A[j] + A[l] + A[r]
				if s < X:
					l += 1
				elif s > X:
					r -= 1
				else:
					l += 1
					r -= 1
					return 1
	return 0


def find4Numbers(A, n, X):
	if n == 4 and sum(A) == X:
		return 1
	elif n == 4 and sum(A) != X:
		return 0
	for i in range(n - 3):
		for j in range(i + 1, n - 2):
			for k in range(j + 1, n - 1):
				s = X - A[i] - A[j] - A[k]
				if s in A[k + 1:]:
					return 1
	return 0


def find4Numbers(A, n, X):
	A.sort()
	i = 0
	k = 0
	l = 0
	for i in range(0, len(A)):
		for j in range(i + 1, len(A)):
			s = j + 1
			end = len(A) - 1
			while s < end:
				k = A[i] + A[j] + A[s] + A[end]
				if k == X:
					return 1
				elif k > X:
					end = end - 1
				else:
					s = s + 1
	return 0


def find4Numbers(A, n, X):
	A.sort()
	for i in range(n - 3):
		for j in range(i + 1, n - 2):
			l = 0
			for k in range(j + 1, n - 1):
				if k + l == n - 1:
					break
				while k + l < n - 2 and A[i] + A[j] + A[k] + A[-l - 1] > X:
					l += 1
				if A[i] + A[j] + A[k] + A[-l - 1] == X:
					return True
	return False


def find4Numbers(A, n, X):
	A.sort()
	for i0 in range(0, n - 3):
		for i1 in range(i0 + 1, n - 2):
			v = X - A[i0] - A[i1]
			if v < 0:
				continue
			(a, b) = (i1 + 1, n - 1)
			while a < b:
				if A[a] + A[b] < v:
					a += 1
				elif A[a] + A[b] > v:
					b -= 1
				else:
					return True
	return False


def find4Numbers(A, n, X):
	f = {}
	for i in range(n):
		if A[i] in f:
			f[A[i]] += 1
		else:
			f[A[i]] = 1
	for i in range(n):
		f[A[i]] -= 1
		for j in range(i + 1, n):
			f[A[j]] -= 1
			for k in range(j + 1, n):
				f[A[k]] -= 1
				if X - (A[i] + A[j] + A[k]) in f:
					if f[X - (A[i] + A[j] + A[k])] >= 1:
						return True
				f[A[k]] += 1
			f[A[j]] += 1
		f[A[i]] += 1
	return False


def find4Numbers(A, n, x):
	A.sort()
	for i in range(n):
		for j in range(i + 1, n):
			next = j + 1
			last = n - 1
			while last > next:
				temp = A[i] + A[j] + A[next] + A[last]
				if temp == x:
					return True
				elif temp > x:
					last -= 1
				else:
					next += 1
	return False


def find4Numbers(A, n, X):
	A.sort()
	for i in range(n - 3):
		for j in range(i + 1, n - 2):
			l = j + 1
			h = n - 1
			while l < h:
				if A[i] + A[j] + A[l] + A[h] == X:
					return 1
				if A[i] + A[j] + A[l] + A[h] < X:
					l += 1
				else:
					h -= 1
	return 0


def find4Numbers(A, n, X):
	A.sort()
	for i in range(n):
		for j in range(i + 1, n):
			nxt = j + 1
			last = n - 1
			while last > nxt:
				temp = A[i] + A[j] + A[nxt] + A[last]
				if temp == X:
					return True
				elif temp > X:
					last -= 1
				else:
					nxt += 1
	return False


def find4Numbers(A, n, X):
	A.sort()
	for i in range(n - 3):
		for j in range(i + 1, n - 2):
			l = j + 1
			m = n - 1
			while l < m:
				if A[i] + A[j] + A[m] + A[l] == X:
					return True
					break
				elif A[i] + A[j] + A[m] + A[l] < X:
					l += 1
				else:
					m -= 1
	return False


def find4Numbers(arr, n, X):
	arr.sort()
	for i in range(n):
		for j in range(i + 1, n):
			l = j + 1
			r = n - 1
			while l < r:
				sum = arr[i] + arr[j] + arr[l] + arr[r]
				if sum == X:
					return 1
				elif sum < X:
					l += 1
				elif sum > X:
					r -= 1
	return 0


def find4Numbers(A, n, X):
	A.sort()
	for i in range(n - 3):
		for j in range(i + 1, n - 2):
			l = j + 1
			r = n - 1
			while l < r:
				curr = A[i] + A[j] + A[l] + A[r]
				if curr == X:
					return True
				elif curr < X:
					l += 1
				else:
					r -= 1
	return 0


def find4Numbers(arr, n, x):
	arr.sort()
	for i in range(n - 3):
		for j in range(i + 1, n - 2):
			k = j + 1
			l = n - 1
			while k < l:
				val = arr[i] + arr[j] + arr[k] + arr[l]
				if val == x:
					return True
				elif val < x:
					k += 1
				else:
					l -= 1
	return False


def find4Numbers(A, n, X):
	for i in range(n):
		for j in range(i + 1, n):
			for k in range(j + 1, n):
				req = X - (A[i] + A[j] + A[k])
				if req in A[k + 1:]:
					return 1
	return 0


def find4Numbers(A, n, X):
	A.sort()
	for i in range(n - 3):
		for j in range(i + 1, n - 2):
			p = j + 1
			q = n - 1
			while p < q:
				if A[i] + A[j] + A[p] + A[q] == X:
					return 1
				elif A[i] + A[j] + A[p] + A[q] < X:
					p += 1
				elif A[i] + A[j] + A[p] + A[q] > X:
					q -= 1
	return 0


def find4Numbers(A, n, X):
	A.sort()
	s = 0
	for i in range(n - 3):
		s = 0
		for j in range(i + 1, n - 2):
			low = j + 1
			high = n - 1
			while low < high:
				s = A[low] + A[high] + A[i] + A[j]
				if s == X:
					return 1
				elif s > X:
					high = high - 1
				else:
					low = low + 1
	return 0


def find4Numbers(A, n, X):
	A.sort()
	one = 2
	two = n - 1
	for i in range(n - 3):
		for j in range(i + 1, n - 2):
			one = j + 1
			two = n - 1
			while one < two:
				sum1 = A[i] + A[j] + A[one] + A[two]
				if sum1 == X:
					return True
				elif sum1 > X:
					two -= 1
				else:
					one += 1
	return False


def find4Numbers(arr, n, X):
	mp = {}
	for i in range(n - 1):
		for j in range(i + 1, n):
			mp[arr[i] + arr[j]] = [i, j]
	for i in range(n - 1):
		for j in range(i + 1, n):
			summ = arr[i] + arr[j]
			if X - summ in mp:
				p = mp[X - summ]
				if p[0] != i and p[0] != j and (p[1] != i) and (p[1] != j):
					return True


def find4Numbers(a, n, x):
	d = {}
	for i in range(n - 1):
		for j in range(i + 1, n):
			summ = a[i] + a[j]
			d[summ] = [i, j]
	for i in range(n - 1):
		for j in range(i + 1, n):
			s = a[i] + a[j]
			if x - s in d:
				p = d[x - s]
				if p[0] != i and p[0] != j and (p[1] != i) and (p[1] != j):
					return True
	return False


def find4Numbers(A, n, X):
	A.sort()
	for j in range(n - 3):
		ans = X - A[j]
		for i in range(j + 1, n - 2):
			val = ans - A[i]
			h = {}
			for k in range(i + 1, n):
				temp = val - A[k]
				if temp in h:
					return True
				else:
					h[A[k]] = 1
	return False


def find4Numbers(arr, n, X):
	ds = {}
	for i in arr:
		ds[i] = ds.get(i, 0) + 1
	for i in range(n):
		for j in range(i + 1, n):
			for k in range(j + 1, n):
				z = arr[i] + arr[j] + arr[k]
				rs = X - z
				cn = 0
				if rs == arr[i]:
					cn += 1
				if rs == arr[j]:
					cn += 1
				if rs == arr[k]:
					cn += 1
				if cn != 0:
					if ds.get(rs, 0) > cn:
						return True
				elif ds.get(rs, 0) > 0:
					return True
	return False


def find4Numbers(A, n, X):
	A.sort()
	for i in range(len(A)):
		for j in range(i + 1, len(A)):
			l = j + 1
			r = n - 1
			while l < r:
				sm = A[i] + A[j] + A[l] + A[r]
				if sm == X:
					return True
				if sm > X:
					r -= 1
				else:
					l += 1
	return False


def find4Numbers(a, n, X):
	for i in range(0, n - 3):
		for j in range(i + 1, n - 2):
			for k in range(j + 1, n - 1):
				if X - a[i] - a[j] - a[k] in set(a[k + 1:]):
					return True
					break
				else:
					continue
	return False


def find4Numbers(A, n, X):
	A.sort()
	for i in range(n):
		for j in range(i + 1, n):
			start = j + 1
			end = n - 1
			while start < end:
				Sum = A[start] + A[end] + A[i] + A[j]
				if Sum == X:
					return 1
				elif Sum < X:
					start += 1
				else:
					end -= 1
	return 0


def find4Numbers(A, n, X):
	A.sort()
	for i in range(n - 3):
		for j in range(i + 1, n - 2):
			l = j + 1
			h = n - 1
			t = X - A[i] - A[j]
			while l < h:
				s = A[l] + A[h]
				if s == t:
					return True
				elif s > t:
					h = h - 1
				else:
					l = l + 1
	return False


def find4Numbers(A, n, X):
	A.sort()
	for i in range(n):
		for j in range(i + 1, n):
			sum = X - A[i] - A[j]
			start = j + 1
			end = n - 1
			while start < end:
				twoSum = A[start] + A[end]
				if twoSum < sum:
					start = start + 1
				elif twoSum > sum:
					end = end - 1
				elif twoSum == sum:
					return True
	return False


def find4Numbers(A, n, X):
	A.sort()
	if n < 4:
		return 0
	elif n == 4 and sum(A) != X:
		return 0
	else:
		for i in range(n - 2):
			for j in range(i + 1, n - 1):
				l = j + 1
				r = n - 1
				while l < r:
					if A[i] + A[j] + A[l] + A[r] == X:
						return 1
					elif A[i] + A[j] + A[l] + A[r] > X:
						r -= 1
					else:
						l += 1
	return 0


def find4Numbers(A, n, X):
	A.sort()
	for i in range(n - 2):
		for j in range(i + 1, n - 1):
			(p, q) = (j + 1, n - 1)
			while p < q:
				temp = A[i] + A[j] + A[p] + A[q]
				if temp == X:
					return True
				elif temp < X:
					p += 1
				else:
					q -= 1
	return False


def find4Numbers(A, n, X):
	A.sort()
	for i in range(n - 3):
		for j in range(i + 1, n - 2):
			k = j + 1
			l = len(A) - 1
			while k < l:
				if A[i] + A[j] + A[k] + A[l] == X:
					return 1
				elif A[i] + A[j] + A[k] + A[l] < X:
					k += 1
				else:
					l -= 1
	return 0


def find4Numbers(A, n, X):
	d = {}
	for i in range(n):
		for j in range(i + 1, n):
			for k in range(j + 1, n):
				z = A[i] + A[j] + A[k]
				if X - z in d:
					return 1
		d[A[i]] = 1
	return 0


def find4Numbers(A, n, X):
	A.sort()
	sum = 0
	for i in range(n - 3):
		for j in range(i + 1, n - 2):
			k = j + 1
			r = n - 1
			while k < r:
				sum = A[i] + A[j] + A[k] + A[r]
				if sum == X:
					return True
				if sum < X:
					k = k + 1
				else:
					r = r - 1
	return False


def find4Numbers(A, n, X):
	for i in range(n):
		for j in range(i + 1, n - 1):
			for k in range(j + 1, n - 1):
				if X - (A[i] + A[j] + A[k]) in A:
					if X - (A[i] + A[j] + A[k]) in [A[i], A[j], A[k]]:
						if A.count(X - (A[i] + A[j] + A[k])) > [A[i], A[j], A[k]].count(X - (A[i] + A[j] + A[k])):
							return 1
					else:
						return 1
	return 0


def find4Numbers(A, n, X):
	A.sort()
	for i in range(n - 3):
		for j in range(i + 1, n - 2):
			s = j + 1
			e = n - 1
			suum = A[i] + A[j]
			while s < e:
				total = A[s] + A[e] + suum
				if total == X:
					return True
				elif total > X:
					e -= 1
				else:
					s += 1
	return False


def find4Numbers(a, n, x):
	a.sort()
	for i in range(n - 3):
		for j in range(i + 1, n - 2):
			t = a[i] + a[j]
			l = j + 1
			r = n - 1
			while l < r:
				s = a[l] + a[r] + t
				if s == x:
					return True
				elif s > x:
					r -= 1
				else:
					l += 1
	return False


def find4Numbers(A, n, X):
	A = sorted(A)
	for i in range(n - 3):
		for j in range(i + 1, n - 2):
			k = j + 1
			l = n - 1
			while k < l:
				add = A[i] + A[j] + A[k] + A[l]
				if add == X:
					return True
				elif add > X:
					l -= 1
				else:
					k += 1
	return False


def find4Numbers(arr, n, X):
	arr.sort()
	for i in range(n):
		add = 0
		for j in range(i + 1, n):
			add = X - arr[i] - arr[j]
			start = j + 1
			end = n - 1
			while start < end:
				two_sum = arr[start] + arr[end]
				if two_sum < add:
					start += 1
				elif two_sum > add:
					end -= 1
				else:
					return True
	return False


def find4Numbers(arr, n, x):
	arr.sort()
	for i in range(n - 3):
		for j in range(i + 1, n - 2):
			Sum = x - (arr[i] + arr[j])
			s = j + 1
			e = n - 1
			while s < e:
				if arr[s] + arr[e] == Sum:
					return True
				elif arr[s] + arr[e] < Sum:
					s += 1
				else:
					e -= 1
	return False


def find4Numbers(A, n, X):
	A.sort()
	for i in range(n):
		for j in range(i + 1, n):
			s = X - A[i] - A[j]
			k = j + 1
			m = n - 1
			while k < m:
				if A[k] + A[m] == s:
					return True
				if A[k] + A[m] < s:
					k += 1
				else:
					m -= 1
	return False