Given an array A of integers, return true if and only if we can partition the array into three non-empty parts with equal sums.
Formally, we can partition the array if we can find indexes i+1 < j with (A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] + A[j-1] + ... + A[A.length - 1])
 
Example 1:
Input: A = [0,2,1,-6,6,-7,9,1,2,0,1]
Output: true
Explanation: 0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1

Example 2:
Input: A = [0,2,1,-6,6,7,9,-1,2,0,1]
Output: false

Example 3:
Input: A = [3,3,6,5,-2,2,5,1,-9,4]
Output: true
Explanation: 3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4

 
Constraints:

3 <= A.length <= 50000
-10^4 <= A[i] <= 10^4

Source: leetcode | Difficulty: EASY
Tags: Data structures

Greedy algorithms

Starter code: class Solution:
    def canThreePartsEqualSum(self, A: List[int]) -> bool:
        

Solutions:
class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		if len(A) < 3:
			return False
		suma = sum(A)
		if suma % 3 != 0:
			return False
		(runsum, target, count) = (0, suma / 3, 0)
		for val in A[:-1]:
			runsum += val
			if runsum == target:
				count += 1
				runsum = 0
				if count == 2:
					return True
		else:
			return False


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		total = sum(A)
		if total % 3 != 0:
			False
		(count, temp, Sum) = (1, total // 3, 0)
		for i in range(len(A) - 1):
			Sum += A[i]
			if Sum == temp * count:
				count += 1
				if count == 3:
					return True
		print(A)
		return False


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		s = 0
		res = 0
		s1 = sum(A)
		if s1 % 3 != 0:
			return False
		target = s1 // 3
		for a in A:
			s += a
			if s == target:
				s = 0
				res += 1
		return res > 2


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		sum = 0
		for i in A:
			sum += i
		s = 0
		c = 0
		for i in A:
			s += i
			if s == int(sum / 3):
				s = 0
				c += 1
		return c >= 3


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		total = sum(A)
		if total % 3 != 0:
			False
		(count, temp, Sum) = (1, total // 3, 0)
		for val in A[:-1]:
			Sum += val
			if Sum == temp:
				Sum = 0
				count += 1
				if count == 3:
					return True
		return False


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		total = sum(A)
		if total % 3 != 0:
			False
		for i in range(1, len(A)):
			A[i] += A[i - 1]
		if total == 0 and A.count(0) < 3:
			return False
		return True if A.count(total // 3) and A.count(total // 3 * 2) and (A.index(total // 3) < len(A) - A[::-1].index(total // 3 * 2)) else False


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		cusum = 0
		cusum_list = list()
		for i in range(len(A)):
			cusum += A[i]
			cusum_list.append(cusum)
		if sum(A) / 3 in cusum_list:
			if sum(A) * 2 / 3 in cusum_list[cusum_list.index(sum(A) / 3) + 1:-1]:
				return True
			else:
				return False
		else:
			return False


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		if sum(A) % 3 != 0:
			return False
		required_sum = sum(A) // 3
		count_partition = 0
		curr_sum = A[0]
		i = 1
		while i < len(A):
			while i < len(A) and curr_sum != required_sum:
				curr_sum += A[i]
				i += 1
			if curr_sum == required_sum:
				count_partition += 1
				if i < len(A):
					curr_sum = A[i]
					i += 1
					if i == len(A) and curr_sum == required_sum:
						count_partition += 1
		if count_partition > 3 and required_sum == 0:
			count_partition = 3
		return count_partition == 3


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		avg = 0
		for i in A:
			avg += i
		if avg % 3 != 0:
			return False
		count = 0
		sum = 0
		for i in range(0, len(A)):
			if sum == avg // 3:
				if i != 0:
					count += 1
					sum = A[i]
			elif sum != avg // 3:
				sum += A[i]
		if sum == avg // 3:
			count += 1
		return count >= 3


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		if sum(A) % 3 != 0:
			return False
		(count, tmp_sum, target) = (0, 0, sum(A) // 3)
		for num in A:
			tmp_sum += num
			if tmp_sum == target:
				count += 1
				tmp_sum = 0
		return count >= 3


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		if len(A) < 3:
			return False
		prefixSumMap = defaultdict(list)
		sumUpto = {}
		total = 0
		for i in range(len(A)):
			prefixSumMap[total].append(i)
			total += A[i]
			sumUpto[i] = total
		s = 0
		for i in range(len(A) - 1, 1, -1):
			s += A[i]
			target = total - 2 * s
			if prefixSumMap.get(target) != None:
				for j in prefixSumMap[target]:
					if j < i and j > 0 and (sumUpto[j - 1] == s):
						return True
		return False


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		sumA = sum(A)
		if sumA % 3 != 0:
			return False
		(tmpSum, isFound, eachPart) = (0, 0, sumA // 3)
		for i in A:
			tmpSum += i
			if tmpSum == eachPart:
				tmpSum = 0
				isFound += 1
		if isFound >= 3:
			return True
		else:
			return False


class Solution:

	def canThreePartsEqualSum(self, A: list) -> bool:
		if len(A) < 3:
			return False
		for i in range(1, len(A)):
			A[i] = A[i - 1] + A[i]
		end_value = A[-1]
		if end_value % 3 != 0:
			return False
		index = len(A) - 2
		while A[index] != 2 * end_value // 3:
			index -= 1
			if index == 0:
				return False
		index -= 1
		while A[index] != end_value // 3:
			index -= 1
			if index < 0:
				return False
		return True


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		d = defaultdict(list)
		sumn = 0
		for (i, num) in enumerate(A):
			sumn += num
			d[sumn].append(i)
		if sumn % 3 != 0:
			return False
		div = sumn // 3
		return div in d and div * 2 in d and (d[div][0] < (d[div * 2][-1] if d[div * 2][-1] != len(A) - 1 else d[div * 2][-2]))


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		s = sum(A)
		if s % 3 != 0:
			return False
		ps = s // 3
		count = 0
		for x in A:
			ps -= x
			if not ps:
				ps = s // 3
				count += 1
				if count > 2:
					return True
		return False


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		s = sum(A)
		if s % 3 != 0:
			return 0
		n = len(A)
		cnt = [0] * n
		s //= 3
		ss = 0
		for i in range(n - 1, -1, -1):
			ss += A[i]
			if i == n - 1:
				cnt[i] = 1 if ss == s else 0
			else:
				cnt[i] = cnt[i + 1] + (1 if ss == s else 0)
		ss = 0
		ans = 0
		print(cnt)
		for i in range(0, n - 2):
			ss += A[i]
			if ss == s:
				ans += cnt[i + 2]
		print(ans)
		return True if ans > 0 else False


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		s = sum(A)
		if s % 3 != 0:
			return False
		x = s // 3
		c = 0
		d = 0
		for a in A[:-1]:
			c += a
			if d == 0 and c == x:
				d = 1
			elif d == 1 and c == 2 * x:
				return True
		return False


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		if sum(A) % 3 != 0:
			return False
		targetSum = sum(A) // 3
		a = 1
		runningSum = A[0]
		while a < len(A) and runningSum != targetSum:
			runningSum += A[a]
			a += 1
		b = len(A) - 2
		runningSum = A[-1]
		while b > -1 and runningSum != targetSum:
			runningSum += A[b]
			b -= 1
		return not a > b


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		if len(A) < 3:
			return False
		for i in range(1, len(A)):
			A[i] = A[i] + A[i - 1]
		sumTarg = A[-1] / 3
		first = False
		for i in range(len(A)):
			if A[i] == sumTarg and first == False:
				first = True
			elif first == True and A[i] == 2 * sumTarg and (i != len(A) - 1):
				return True
		return False


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		cummulative_sum = 0
		counter = 0
		target = sum(A) / 3
		if target != int(target):
			return False
		print(target)
		for idx in range(len(A)):
			cummulative_sum += A[idx]
			if cummulative_sum == target:
				cummulative_sum = 0
				counter += 1
		if counter == 4 and target == 0:
			return True
		if counter == 3:
			return True
		return False


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		if sum(A) - sum(A) // 3 * 3 != 0:
			return 0
		else:
			s = sum(A) // 3
			c = 0
			ts = 0
			j = 0
			for i in range(len(A)):
				j = i
				ts += A[i]
				if ts == s:
					c += 1
					ts = 0
				if c == 2 and j + 1 < len(A):
					for k in range(j + 1, len(A)):
						ts += A[k]
					if ts == s:
						return 1
					else:
						return 0
			return 0


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		partSum = sum(A) / 3
		curSum = 0
		partNum = 0
		for i in A:
			curSum += i
			if curSum == partSum:
				curSum = 0
				partNum += 1
		if partSum == 0:
			return partNum >= 3
		else:
			return partNum == 3


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		total = sum(A)
		third = total // 3
		(cumsum, count) = (0, 0)
		for i in range(0, len(A)):
			cumsum += A[i]
			if cumsum == third:
				count += 1
				cumsum = 0
		return count == 3 or (count > 3 and total == 0)


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		x = 0
		for i in A:
			x += i
		if x % 3 != 0:
			return False
		x = x / 3
		count = 0
		sum1 = 0
		for i in A:
			sum1 += i
			if sum1 == x:
				count += 1
				sum1 = 0
		if count >= 3:
			return True
		else:
			return False


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		total = sum(A)
		if total % 3 != 0:
			return False
		i = 0
		count = A[i]
		while i < len(A) - 1 and count != total / 3:
			i += 1
			count += A[i]
		if count != total / 3 or i + 1 > len(A) - 2:
			return False
		j = i + 1
		count = A[j]
		while j < len(A) - 1 and count != total / 3:
			j += 1
			count += A[j]
		if count != total / 3 or j + 1 == len(A):
			return False
		if sum(A[j + 1:]) == total / 3:
			return True
		else:
			return False


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		equalSum = sum(A) // 3
		part = 0
		numparts = 0
		r = sum(A) % 3
		for i in A:
			part += i
			if part == equalSum:
				part = 0
				numparts += 1
		return not r and numparts >= 3


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		sum1 = sum(A)
		if sum1 % 3 != 0:
			return False
		else:
			div = sum1 // 3
			print(div)
			(i1, sum2) = (0, 0)
			for i in A:
				sum2 = sum2 + i
				print(sum2, i)
				if sum2 == div:
					i1 = i1 + 1
					print('sum2', sum2)
					sum2 = 0
			if i1 >= 3 and div == 0:
				return True
			if i1 == 3:
				return True
			return False


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		total = sum(A)
		isum = 0
		for i in range(0, len(A) - 2):
			isum += A[i]
			if isum == total / 3:
				jsum = 0
				for j in range(i + 1, len(A) - 1):
					jsum += A[j]
					if isum == jsum == total - isum - jsum:
						return True
		return False


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		j = len(A)
		i = 0
		num = sum(A) // 3
		print(num)
		sum1 = 0
		sum2 = 0
		sum3 = 0
		for i in range(0, j):
			sum1 = sum1 + A[i]
			i = i + 1
			if sum1 == num:
				break
		for i in range(i, j):
			sum2 = sum2 + A[i]
			i = i + 1
			if sum2 == num:
				break
		if i == j:
			return False
		sum3 = sum(A[i:])
		return sum1 == sum2 and sum1 == sum3


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		s = sum(A)
		if s % 3 != 0:
			return False
		flag = 0
		temp = 0
		for i in range(len(A)):
			temp += A[i]
			if flag == 0 and temp == s // 3:
				flag += 1
			elif flag == 1 and temp == s * 2 / 3 and (i != len(A) - 1):
				return True
		return False


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		(average, remainder, part, cnt) = (sum(A) // 3, sum(A) % 3, 0, 0)
		for a in A:
			part += a
			if part == average:
				cnt += 1
				part = 0
		return not remainder and cnt >= 3


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		total = sum(A)
		curr_sum = 0
		first_found_flag = False
		for i in range(len(A) - 1):
			curr_sum += A[i]
			if not first_found_flag:
				if curr_sum == total / 3:
					first_found_flag = True
			elif curr_sum == total * 2 / 3:
				return True
		return False


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		(l, r, s) = (1, len(A) - 2, sum(A))
		(ls, rs, avgs) = (A[0], A[-1], s // 3)
		while l < r:
			if l < r and ls != avgs:
				ls += A[l]
				l += 1
			if l < r and rs != avgs:
				rs += A[r]
				r -= 1
			if ls == rs == avgs and s % 3 == 0:
				return True
		return False


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		t = sum(A)
		if t % 3 != 0:
			return False
		s = 0
		p = 0
		for i in range(len(A)):
			s += A[i]
			if s == t // 3:
				s = 0
				p += 1
		if p >= 3:
			return True
		return False


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		s = sum(A)
		if s % 3 != 0:
			return False
		s = s / 3
		t = 0
		count = 0
		for x in A:
			t += x
			if t == s:
				t = 0
				count += 1
		if t == 0 and count >= 3:
			return True
		else:
			return False


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		s = sum(A)
		if s % 3 != 0:
			return False
		target = s // 3
		current = 0
		count = 0
		for v in A:
			current += v
			if current == target:
				count += 1
				current = 0
				if count >= 3:
					return True
		return False


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		totalSum = sum(A)
		if totalSum % 3 != 0:
			return False
		target = totalSum // 3
		numPartitions = 0
		currSum = 0
		for num in A:
			currSum += num
			if currSum == target:
				numPartitions += 1
				currSum = 0
				if numPartitions == 3:
					return True
		return False


class Solution:

	def canThreePartsEqualSum(self, li: List[int]) -> bool:
		s = sum(li)
		if s % 3:
			return False
		ts = s // 3
		ss = 0
		chunk = 0
		for n in li[:-1]:
			ss += n
			if ss == ts:
				chunk += 1
				if chunk == 2:
					return True
				ss = 0
		return False


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		s = sum(A)
		if s % 3 != 0:
			return False
		(curr, target) = (0, s // 3)
		count = 0
		for ix in range(len(A)):
			curr += A[ix]
			if curr == target:
				curr = 0
				count += 1
			if count == 2 and ix < len(A) - 1:
				return True
		return False


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		total = sum(A)
		if total % 3 != 0:
			return False
		partition_sum = total / 3
		numberofpartition = 0
		tempsum = 0
		for i in range(len(A)):
			tempsum += A[i]
			if tempsum == partition_sum:
				numberofpartition += 1
				tempsum = 0
			if numberofpartition == 3:
				return True
		return False


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		S = sum(A)
		if S % 3 != 0:
			return False
		S_1 = S / 3
		S_2 = S_1 + S_1
		cur = A[0]
		for i in range(1, len(A) - 2):
			if cur == S_1:
				cur += A[i]
				for j in range(i + 1, len(A) - 1):
					if cur == S_2:
						return True
					else:
						cur += A[j]
				if cur == S_2:
					return A[-1] == S_1
			else:
				cur += A[i]
		if cur == S_1:
			return A[-1] == S_1
		return False


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		tot = sum(A)
		if tot % 3 != 0:
			return False
		flag = 0
		temp_tot = 0
		presum = [0] * (len(A) + 1)
		s = tot // 3
		target = [2 * s, s]
		for i in range(len(A)):
			if not target:
				return True
			presum[i + 1] = presum[i] + A[i]
			if presum[i + 1] == target[-1]:
				target.pop()
		return False


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		if sum(A) % 3:
			return False
		sumParts = sum(A) // 3
		summ = 0
		parts = 0
		for num in A:
			summ += num
			if summ == sumParts:
				parts += 1
				summ = 0
		return parts >= 3


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		sum = 0
		for a in A:
			sum += a
		target = floor(sum / 3)
		sum = 0
		cnt = 0
		j = len(A) - 1
		i = 0
		while j > 0:
			sum += A[j]
			if sum == target:
				cnt += 1
				sum = 0
				break
			j -= 1
		while i < j:
			sum += A[i]
			if cnt < 2 and sum == target:
				cnt += 1
				sum = 0
				if j - i <= 1:
					return False
			i += 1
			if i >= j:
				break
		if cnt == 2 and sum == target:
			cnt += 1
		if cnt == 3:
			return True
		return False


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		s = sum(A)
		if s % 3 != 0:
			return False
		return self.can_partition(A, 0, 3, s // 3)

	def can_partition(self, A: List[int], i: int, n_parts: int, target_sum: int) -> bool:
		if n_parts == 1:
			return i < len(A) and sum(A[i:]) == target_sum
		if i >= len(A):
			return False
		partition_sum = A[i]
		j = i + 1
		while j < len(A) and partition_sum != target_sum:
			partition_sum += A[j]
			j += 1
		return self.can_partition(A, j, n_parts - 1, target_sum)


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		sum = 0
		for num in A:
			sum += num
		if sum % 3 != 0:
			return False
		sum = sum / 3
		total = 0
		currentSum = 0
		for num in A:
			currentSum += num
			if currentSum == sum:
				total += 1
				currentSum = 0
		return True if total >= 3 else False


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		tot = sum(A)
		if tot % 3 != 0:
			return False
		target = tot // 3
		curr_sum = 0
		(check1, check2) = (0, 0)
		for (i, a) in enumerate(A):
			curr_sum += a
			if check1 != 1 and curr_sum == target:
				check1 = 1
				continue
			if check1 and curr_sum == target * 2 and (i < len(A) - 1):
				check2 = 1
				break
		if check1 and check2:
			return True
		else:
			return False


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		s = sum(A)
		s1 = 0
		i = 0
		print(s // 3)
		while i < len(A):
			s1 += A[i]
			if s1 == s // 3:
				break
			i += 1
		s1 = 0
		i += 1
		while i < len(A):
			s1 += A[i]
			print(s1)
			if s1 == s // 3:
				if i != len(A) - 1:
					return True
			i += 1
		return False


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		tot = 0
		bi = sum(A) // 3
		count = 0
		for i in range(len(A) - 1):
			tot += A[i]
			if tot == bi:
				tot = 0
				count += 1
				if count == 2:
					return True
		return False


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		total = sum(A)
		if total % 3 != 0:
			return False
		target = total / 3
		print(target)
		temp = 0
		res = []
		for (i, v) in enumerate(A):
			temp = temp + v
			if temp == target:
				res.append(i)
				temp = 0
		print(res)
		return len(res) >= 3


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		s = sum(A)
		if s % 3 != 0:
			return False
		target = s / 3
		total = 0
		partitions = 0
		for num in A:
			total += num
			if total == target:
				partitions += 1
				total = 0
		return total == 0 and partitions in [3, 4]


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		n = len(A)
		sum_a = sum(A)
		if sum_a % 3 != 0:
			return False
		target = sum_a // 3
		output = []
		temp_sum = 0
		temp_output = []
		for i in A:
			temp_output.append(i)
			temp_sum = temp_sum + i
			if temp_sum == target:
				if len(temp_output) > 0 and len(output) < 3:
					output.append(temp_output)
					temp_sum = 0
					temp_output = []
		if temp_sum != 0:
			return False
		if len(output) != 3:
			return False
		else:
			return True


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		tot_sum = sum(A)
		if tot_sum % 3 != 0:
			return False
		else:
			cum_sum = 0
			target = tot_sum // 3
			counter = 0
			for num in A[:-1]:
				cum_sum += num
				if cum_sum == target:
					counter += 1
					cum_sum = 0
					if counter == 2:
						return True
			return False


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		total = sum(A)
		if total % 3 != 0:
			return False
		subtotal = total // 3
		pre_sum = 0
		k = 3
		for i in range(len(A)):
			pre_sum += A[i]
			if k > 1 and pre_sum == subtotal:
				k -= 1
				pre_sum = 0
			elif i == len(A) - 1:
				k -= 1
		return k == 0 and pre_sum == subtotal


class Solution:

	def canThreePartsEqualSum(self, A: List[int]) -> bool:
		if sum(A) % 3 != 0:
			return False
		val = sum(A) // 3
		add = 0
		count = 0
		for x in range(len(A)):
			add += A[x]
			if add == val:
				add = 0
				count += 1
			else:
				continue
		if count >= 3:
			return True
		return False