Given an integer array a[ ] of N elements and an integer K, the task is to check if the array a[ ] could be divided into K non-empty subsets with equal sum of elements.
Note: All elements of this array should be part of exactly one partition.
Example 1:
Input: 
N = 5
a[] = {2,1,4,5,6}
K = 3
Output: 
1
Explanation: we can divide above array 
into 3 parts with equal sum as (2, 4), 
(1, 5), (6)
Example 2:
Input: 
N = 5 
a[] = {2,1,5,5,6}
K = 3
Output: 
0
Explanation: It is not possible to divide
above array into 3 parts with equal sum.
Your Task:
You don't need to read input or print anything. Your task is to complete the function isKPartitionPossible() which takes the array a[], the size of the array N, and the value of K as inputs and returns true(same as 1) if possible, otherwise false(same as 0).
Expected Time Complexity: O(N*2^{N}).
Expected Auxiliary Space: O(2^{N}).
Constraints:
1 ≤ K ≤ N ≤ 10
1 ≤ a[i] ≤ 100

Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Complete search
Skill types: Dynamic programming

Complete search
Expected Time Complexity: O(N*2^{N}).
Expected Auxiliary Space: O(2^{N}).

Starter code:
#User function Template for python3



class Solution:

    def isKPartitionPossible(self, a, k):

        #code here

Solutions:
class Solution:

	def isKPartitionPossible(self, a, k):
		if sum(a) % k != 0:
			return False
		target = sum(a) // k
		used = [False for i in range(len(a))]

		def backtrack(index, k, subsetSum):
			if k == 0:
				return True
			if subsetSum == target:
				return backtrack(0, k - 1, 0)
			for j in range(index, len(a)):
				if used[j] == True or subsetSum + a[j] > target:
					continue
				used[j] = True
				if backtrack(index + 1, k, subsetSum + a[j]):
					return True
				used[j] = False
			return False
		return backtrack(0, k, 0)


class Solution:

	def isKPartitionPossible(self, a, k):
		n = len(a)
		target = sum(a) / k
		subSets = [0] * k

		def recurse(i):
			if i == n:
				return True
			for j in range(k):
				if subSets[j] + a[i] <= target:
					subSets[j] += a[i]
					if recurse(i + 1):
						return True
					subSets[j] -= a[i]
					if subSets[j] == 0:
						break
			return False
		return recurse(0)


def helper(i, reqSum, nums, subset, k):
	if i == len(nums):
		return True
	for j in range(k):
		if subset[j] + nums[i] <= reqSum:
			subset[j] += nums[i]
			if helper(i + 1, reqSum, nums, subset, k):
				return True
			subset[j] -= nums[i]
			if subset[j] == 0:
				break
	return False

class Solution:

	def isKPartitionPossible(self, nums, k):
		n = len(nums)
		subset = [0] * k
		if sum(nums) % k != 0:
			return False
		reqSum = sum(nums) // k
		nums.sort(reverse=True)
		return helper(0, reqSum, nums, subset, k)


class Solution:

	def isKPartitionPossible(self, nums, k):
		total = sum(nums)
		if total % k:
			return False
		reqSum = total / k
		subSets = [0] * k
		nums.sort(reverse=True)

		def recurse(i):
			if i == len(nums):
				return True
			for j in range(k):
				if subSets[j] + nums[i] <= reqSum:
					subSets[j] += nums[i]
					if recurse(i + 1):
						return True
					subSets[j] -= nums[i]
					if subSets[j] == 0:
						break
			return False
		return recurse(0)


def k_subset_possible(input_arr: [], index, n, k, result_arr: [], sum_path_arr: [], required_sum):
	if index > n:
		return
	if index == n:
		for i in range(k):
			element = sum_path_arr[i]
			if element != required_sum:
				return
		result_arr[0] = True
		return
	element = input_arr[index]
	for i in range(k):
		sum_value = sum_path_arr[i]
		if sum_value == 0:
			sum_path_arr[i] = element
			k_subset_possible(input_arr, index + 1, n, k, result_arr, sum_path_arr, required_sum)
			sum_path_arr[i] = sum_path_arr[i] - element
			break
		else:
			sum_path_arr[i] = sum_path_arr[i] + element
			k_subset_possible(input_arr, index + 1, n, k, result_arr, sum_path_arr, required_sum)
			sum_path_arr[i] = sum_path_arr[i] - element

def partition_sum_k_driver(input_arr: [], k):
	n = len(input_arr)
	sum_value = sum(input_arr)
	if k == 1:
		return True
	if k == n:
		for element in input_arr:
			if element != sum_value // k:
				return False
		return True
	required_sum = sum_value // k
	if sum_value % k != 0:
		return
	sum_path_arr = [0] * k
	result_arr = [False]
	k_subset_possible(input_arr, 0, n, k, result_arr, sum_path_arr, required_sum)
	return result_arr[0]

class Solution:

	def isKPartitionPossible(self, a, k):
		return partition_sum_k_driver(a, k)


class Solution:

	def isKPartitionPossible(self, a, k):
		if k < 2:
			return k
		if sum(a) % k:
			return False
		n = len(a)
		arr = [False] * n

		def helper(summ, s, k, arr, ind, n, a):
			if k == 1:
				return True
			if summ > s:
				return False
			if summ == s:
				return helper(0, s, k - 1, arr, 0, n, a)
			for i in range(ind, n):
				if not arr[i]:
					arr[i] = True
					if helper(summ + a[i], s, k, arr, i + 1, n, a):
						return True
					arr[i] = False
			return False
		return helper(0, sum(a) // k, k, arr, 0, n, a)


def kPartation(arr, i, k):
	if i >= len(arr):
		for j in range(1, len(k)):
			if k[j - 1] != k[j]:
				return False
		return True
	res = False
	for n in range(len(k)):
		if k[n] == 0:
			k[n] = k[n] + arr[i]
			res = res or kPartation(arr, i + 1, k)
			if res == True:
				return True
			k[n] = k[n] - arr[i]
			break
	for j in range(len(k)):
		if k[j] != 0:
			k[j] = k[j] + arr[i]
			res = res or kPartation(arr, i + 1, k)
			if res == True:
				return True
			k[j] = k[j] - arr[i]
	return False

def controllerKpartation(arr, k):
	kAry = [0 for i in range(k)]
	return kPartation(arr, 0, kAry)

class Solution:

	def isKPartitionPossible(self, a, k):
		return controllerKpartation(arr, k)


class Solution:

	def isKPartitionPossible(self, a, k):
		if sum(a) % k:
			return False
		a.sort()
		visited = set()
		target = sum(a) / k

		def backtrack(idx, count, currsum):
			if count == k:
				return True
			if currsum == target:
				return backtrack(0, count + 1, 0)
			for i in range(idx, len(a)):
				if i > 0 and i - 1 not in visited and (a[i] == a[i - 1]):
					continue
				if i in visited or currsum + a[i] > target:
					continue
				visited.add(i)
				if backtrack(i + 1, count, currsum + a[i]):
					return True
				visited.remove(i)
			return False
		return backtrack(0, 0, 0)


class Solution:

	def isKPartitionPossible(self, a, k):
		res = []

		def solve(a, s, p, k, vis, i, n):
			if k == 0:
				return True
			if s > p:
				return False
			if s == p:
				return solve(a, 0, p, k - 1, vis, 0, n)
			for i in range(i, n):
				if vis[i]:
					continue
				vis[i] = True
				if solve(a, s + a[i], p, k, vis, i + 1, n):
					return True
				vis[i] = False
			return False
		s = sum(a)
		if s % k != 0:
			return False
		n = len(a)
		vis = [0] * n
		return solve(a, 0, s // k, k, vis, 0, n)


class Solution:

	def isKPartitionPossible(self, a, k):
		s = sum(a)
		if s % k != 0:
			return 0
		s = s // k

		def manu(i, subnum, picked, s, cursum):
			if subnum == k + 1:
				return True
			if cursum == s:
				return manu(0, subnum + 1, picked, s, 0)
			elif cursum > s:
				return False
			if i >= len(a):
				return False
			if picked[i] == 1:
				return manu(i + 1, subnum, picked, s, cursum)
			else:
				cursum += a[i]
				picked[i] = 1
				k1 = manu(i + 1, subnum, picked, s, cursum)
				cursum -= a[i]
				picked[i] = 0
				k2 = manu(i + 1, subnum, picked, s, cursum)
				return k1 or k2
		picked = [0 for i in range(len(a))]
		return manu(0, 1, picked, s, 0)


class Solution:

	def isKPartitionPossible(self, nums, k):
		nums.sort()
		(target, rem) = divmod(sum(nums), k)
		if rem or nums[-1] > target:
			return False
		dp = [False] * (1 << len(nums))
		dp[0] = True
		total = [0] * (1 << len(nums))
		for state in range(1 << len(nums)):
			if not dp[state]:
				continue
			for (i, num) in enumerate(nums):
				future = state | 1 << i
				if state != future and (not dp[future]):
					if num <= target - total[state] % target:
						dp[future] = True
						total[future] = total[state] + num
					else:
						break
		return dp[-1]


def isKPartitionPossibleRec(arr, subsetSum, taken, subset, K, N, curIdx, limitIdx):
	if subsetSum[curIdx] == subset:
		if curIdx == K - 2:
			return True
		return isKPartitionPossibleRec(arr, subsetSum, taken, subset, K, N, curIdx + 1, N - 1)
	for i in range(limitIdx, -1, -1):
		if taken[i]:
			continue
		tmp = subsetSum[curIdx] + arr[i]
		if tmp <= subset:
			taken[i] = True
			subsetSum[curIdx] += arr[i]
			nxt = isKPartitionPossibleRec(arr, subsetSum, taken, subset, K, N, curIdx, i - 1)
			taken[i] = False
			subsetSum[curIdx] -= arr[i]
			if nxt:
				return True
	return False

def isKPartitionPossiblee(arr, N, K):
	if K == 1:
		return True
	if N < K:
		return False
	sum = 0
	for i in range(N):
		sum += arr[i]
	if sum % K != 0:
		return False
	subset = sum // K
	subsetSum = [0] * K
	taken = [0] * N
	for i in range(K):
		subsetSum[i] = 0
	for i in range(N):
		taken[i] = False
	subsetSum[0] = arr[N - 1]
	taken[N - 1] = True
	return isKPartitionPossibleRec(arr, subsetSum, taken, subset, K, N, 0, N - 1)

class Solution:

	def isKPartitionPossible(self, nums, k):
		return isKPartitionPossiblee(nums, len(nums), k)


class Solution:

	def isKPartitionPossible(self, a, k):

		def help(i):
			if i == len(a):
				for i in arr:
					if i != n:
						return False
				return True
			for j in range(len(arr)):
				if arr[j] + a[i] <= n:
					arr[j] += a[i]
					if help(i + 1):
						return 1
					arr[j] -= a[i]
					if arr[j] == 0:
						return 0
			return 0
		n = sum(a) / k
		if k > n or sum(a) // k != n:
			return 0
		arr = [0] * k
		if help(0):
			return 1
		return 0


from functools import lru_cache

class Solution:

	def isKPartitionPossible(self, a, k):

		def help(i):
			if i == len(a):
				for i in arr:
					if i != n:
						return False
				return True
			for j in range(len(arr)):
				if arr[j] + a[i] <= n:
					arr[j] += a[i]
					if help(i + 1):
						return 1
					arr[j] -= a[i]
					if arr[j] == 0:
						break
			return 0
		n = sum(a) / k
		if k > n or sum(a) // k != n:
			return 0
		arr = [0] * k
		if help(0):
			return 1
		return 0


class Solution:

	def __init__(self):
		self.flag = False

	def KPartition(self, indx, n, a, k, subsetsum, dp, nos):
		if indx == n:
			if nos == k:
				for i in range(k - 1):
					if subsetsum[i] != subsetsum[i + 1]:
						return
				self.flag = True
			return
		for i in range(k):
			if len(dp[i]) == 0:
				subsetsum[i] += a[indx]
				dp[i].append(a[indx])
				self.KPartition(indx + 1, n, a, k, subsetsum, dp, nos + 1)
				subsetsum[i] -= a[indx]
				dp[i].pop()
				break
			else:
				subsetsum[i] += a[indx]
				dp[i].append(a[indx])
				self.KPartition(indx + 1, n, a, k, subsetsum, dp, nos)
				subsetsum[i] -= a[indx]
				dp[i].pop()

	def isKPartitionPossible(self, a, k):
		subsetsum = [0] * k
		dp = [[] for i in range(k)]
		self.KPartition(0, len(a), a, k, subsetsum, dp, 0)
		return self.flag


class Solution:

	def __init__(self):
		self.flag = False

	def KPartition(self, indx, nos, k, n, a, sum, ans):
		if indx == n:
			if nos == k:
				f = True
				for i in range(k - 1):
					if sum[i] != sum[i + 1]:
						f = False
						break
				if f == True:
					self.flag = True
			return
		for i in range(k):
			if len(ans[i]) > 0:
				ans[i].append(a[indx])
				sum[i] += a[indx]
				self.KPartition(indx + 1, nos, k, n, a, sum, ans)
				ans[i].pop()
				sum[i] -= a[indx]
			else:
				ans[i].append(a[indx])
				sum[i] += a[indx]
				self.KPartition(indx + 1, nos + 1, k, n, a, sum, ans)
				ans[i].pop()
				sum[i] -= a[indx]
				break

	def isKPartitionPossible(self, a, k):
		self.flag = False
		n = len(a)
		ans = [[] for _ in range(k)]
		sum = [0] * k
		self.KPartition(0, 0, k, n, a, sum, ans)
		return self.flag


class Solution:

	def isKPartitionPossible(self, a, k):
		a.sort(reverse=True)
		summa = sum(a)
		target = summa // k
		if summa % k or max(a) > target:
			return 0
		output = 0
		for item in a:
			output += self.helper(item, item, target, a.copy())
		return output

	def helper(self, summa, last, target, a):
		a.remove(last)
		if not a:
			return 1
		if summa == target:
			summa = 0
		for item in a:
			if item + summa <= target and self.helper(summa + item, item, target, a.copy()):
				return 1
		return 0


class Solution:

	def isKPartitionPossible(self, a, k):
		n = len(a)
		target = sum(a) // k
		subset = [False] * n
		if sum(a) % k:
			return False

		def recur(ind, k, subsetsum):
			if k == 0:
				return True
			if subsetsum == target:
				return recur(0, k - 1, 0)
			for i in range(ind, n):
				if subset[i] or subsetsum + a[i] > target:
					continue
				subset[i] = True
				if recur(ind + 1, k, subsetsum + a[i]):
					return True
				subset[i] = False
			return False
		return recur(0, k, 0)


class Solution:

	def recsol2(self, set_arr, set_idx, set_sum, req_sum, k, istaken):
		if set_sum == req_sum:
			if set_idx == k - 2:
				return True
			return self.recsol2(set_arr, set_idx + 1, 0, req_sum, k, istaken)
		for j in range(len(set_arr)):
			if istaken[j] == False and req_sum >= set_sum + set_arr[j]:
				istaken[j] = True
				found = self.recsol2(set_arr, set_idx, set_sum + set_arr[j], req_sum, k, istaken)
				istaken[j] = False
				if found == True:
					return True
		return False

	def isKPartitionPossible(self, a, k):
		if k == 1:
			return 1
		if k > len(a):
			return 0
		if sum(a) % k != 0:
			return 0
		req_sum = sum(a) // k
		istaken = [False] * len(a)
		istaken[0] = True
		if self.recsol2(a, 0, a[0], req_sum, k, istaken) == True:
			return 1
		return 0


class Solution:

	def isKPartitionPossible(self, a, k):
		total = sum(a)
		if total % k:
			return False
		a.sort(reverse=True)
		target = total // k
		subsets = [0] * k

		def backtrack(i):
			if i == len(a):
				return True
			for j in range(k):
				if subsets[j] + a[i] <= target:
					subsets[j] += a[i]
					if backtrack(i + 1):
						return True
					subsets[j] -= a[i]
					if subsets[j] == 0:
						break
			return False
		return backtrack(0)


class Solution:

	def solvepartition(self, idx, a, k, reqdsum, used, subsetsum):
		if k == 0:
			return True
		if subsetsum == reqdsum:
			return self.solvepartition(0, a, k - 1, reqdsum, used, 0)
		for i in range(idx, len(arr)):
			if i > 0 and (not used[i - 1]) and (arr[i] == arr[i - 1]):
				continue
			if used[i] or subsetsum + arr[i] > reqdsum:
				continue
			used[i] = True
			if self.solvepartition(i + 1, a, k, reqdsum, used, subsetsum + arr[i]):
				return True
			used[i] = False
		return False

	def isKPartitionPossible(self, a, k):
		total = sum(a)
		reqdsum = total / k
		if total % k == 1:
			return False
		used = [False] * len(a)
		arr.sort()
		if self.solvepartition(0, a, k, reqdsum, used, 0):
			return 1
		return 0


class Solution:

	def isKPartitionPossible(self, a, k):

		def foo(a, i, k, n, grp, g):
			if n == i:
				return len(set(grp)) == 1
			for j in range(k):
				if grp[j] + a[i] > g:
					continue
				grp[j] += a[i]
				res = foo(a, i + 1, k, n, grp, g)
				if res:
					return True
				grp[j] -= a[i]
			return False
		n = len(a)
		if sum(a) / k % 1 != 0 or max(a) > sum(a) // k or n < k:
			return False
		grp = [0 for i in range(k)]
		return foo(a, 0, k, n, grp, sum(a) // k)


class Solution:

	def solve(self, arr, idx, k, curSum, target, taken):
		if k == 0:
			return 1
		if curSum == target:
			return self.solve(arr, 0, k - 1, 0, target, taken)
		for j in range(idx, len(arr)):
			if taken[j] == True or curSum + arr[j] > target:
				continue
			taken[j] = True
			if self.solve(arr, idx + 1, k, curSum + arr[j], target, taken):
				return True
			taken[j] = False

	def isKPartitionPossible(self, a, k):
		if k == 1:
			return 1
		n = len(a)
		if n < k:
			return 0
		summ = sum(a)
		if summ % k != 0:
			return 0
		taken = [False] * n
		target = summ // k
		return self.solve(a, 0, k, 0, target, taken)


class Solution:

	def part(self, i, a, k, target, subsetsum, used):
		if k == 0:
			return True
		if subsetsum == target:
			return self.part(0, a, k - 1, target, 0, used)
		for j in range(i, len(a)):
			if a[j] + subsetsum > target or used[j] == True:
				continue
			used[j] = True
			if self.part(j + 1, a, k, target, subsetsum + a[j], used):
				return True
			used[j] = False
		return False

	def isKPartitionPossible(self, a, k):
		sumi = sum(a)
		if sumi % k != 0:
			return 0
		else:
			target = sumi // k
			used = [False for i in range(len(a))]
			return self.part(0, a, k, target, 0, used)


from collections import defaultdict

class Solution:

	def isKPartitionPossible(self, arr, K):
		N = len(arr)
		if K == 1:
			return True
		if N < K:
			return False
		sum = 0
		for i in range(N):
			sum += arr[i]
		if sum % K != 0:
			return False
		subset = sum // K
		subsetSum = [0] * K
		taken = [0] * N
		for i in range(K):
			subsetSum[i] = 0
		for i in range(N):
			taken[i] = False
		subsetSum[0] = arr[N - 1]
		taken[N - 1] = True

		def isKPartitionPossibleRec(arr, subsetSum, taken, subset, K, N, curIdx, limitIdx):
			if subsetSum[curIdx] == subset:
				if curIdx == K - 2:
					return True
				return isKPartitionPossibleRec(arr, subsetSum, taken, subset, K, N, curIdx + 1, N - 1)
			for i in range(limitIdx, -1, -1):
				if taken[i]:
					continue
				tmp = subsetSum[curIdx] + arr[i]
				if tmp <= subset:
					taken[i] = True
					subsetSum[curIdx] += arr[i]
					nxt = isKPartitionPossibleRec(arr, subsetSum, taken, subset, K, N, curIdx, i - 1)
					taken[i] = False
					subsetSum[curIdx] -= arr[i]
					if nxt:
						return True
			return False
		return isKPartitionPossibleRec(arr, subsetSum, taken, subset, K, N, 0, N - 1)


class Solution:

	def isKPartitionPossible(self, a, k):
		_sum = sum(a)
		n = len(a)
		if n < k or _sum % k != 0:
			return False
		target = _sum // k
		used = [False] * n

		def helper(sum, index, id):
			nonlocal a, n, k, target, used
			if sum == target:
				if id == k:
					return True
				else:
					return helper(0, 0, id + 1)
			elif sum > target:
				return False
			else:
				for i in range(index, n):
					if used[i] == False:
						used[i] = True
						if helper(sum + a[i], i + 1, id):
							return True
						used[i] = False
				return False
		return helper(0, 0, 1)


class Solution:

	def solve(self, arr, ind, sum1, tar, k):
		if k == 0:
			return True
		if sum1 == tar:
			return self.solve(arr, 0, 0, tar, k - 1)
		for j in range(ind, len(arr)):
			if vis[j] or arr[j] + sum1 > tar:
				continue
			vis[j] = 1
			if self.solve(arr, j + 1, sum1 + arr[j], tar, k):
				return True
			vis[j] = 0
		return False

	def isKPartitionPossible(self, arr, k):
		n = len(arr)
		global vis
		vis = [0 for i in range(n)]
		if k == 1:
			return True
		if k > n:
			return False
		sum1 = sum(arr)
		if sum1 % k != 0:
			return False
		return self.solve(arr, 0, 0, sum1 // k, k)


class Solution:

	def isKPartitionPossible(self, a, k):
		if not a:
			return
		s = sum(a)
		if s % k != 0:
			return False
		div = s // k
		sides = [0] * k
		a.sort(reverse=True)

		def dfs(i):
			if i == len(a):
				return True
			for j in range(k):
				if sides[j] + a[i] <= div:
					if j > 0 and sides[j] == sides[j - 1]:
						continue
					sides[j] += a[i]
					if dfs(i + 1):
						return True
					sides[j] -= a[i]
			return False
		return dfs(0)


class Solution:

	def isKPartitionPossible(self, a, k):
		n = len(a)
		target = sum(a) // k
		subset = [0] * k

		def func(ind, n, k, a, taregt, subset):
			if ind == n:
				return True
			for j in range(k):
				if subset[j] + a[ind] <= target:
					subset[j] += a[ind]
					if func(ind + 1, n, k, a, target, subset):
						return True
					subset[j] -= a[ind]
					if subset[j] == 0:
						break
			return False
		return func(0, n, k, a, target, subset)


class Solution:

	def isKPartitionPossible(self, a, k):
		n = len(a)
		used = [False] * n
		if sum(a) % k:
			return False
		target = sum(a) // k

		def dfs(ind, total, k):
			if k == 0:
				return True
			if total == 0:
				return dfs(0, target, k - 1)
			for j in range(ind, len(a)):
				if j > 0 and (not used[j - 1]) and (a[j] == a[j - 1]):
					continue
				if used[j] or total - a[j] < 0:
					continue
				used[j] = True
				if dfs(j + 1, total - a[j], k):
					return True
				used[j] = False
			return False
		return dfs(0, target, k)


class Solution:

	def isKPartitionPossible(self, a, k):
		s = sum(a)
		if s % k != 0:
			return False
		e = s / k
		a.sort(reverse=True)
		visited = [False] * len(a)

		def dfs(kleft, cursum, start):
			if kleft == 1:
				return True
			if cursum == e:
				return dfs(kleft - 1, 0, 0)
			for i in range(start, len(a)):
				if not visited[i] and cursum + a[i] <= e:
					visited[i] = True
					if dfs(kleft, cursum + a[i], i + 1):
						return True
					visited[i] = False
			return False
		return dfs(k, 0, 0)


class Solution:

	def isKPartitionPossible(self, a, k):
		if not sum(a) % k == 0:
			return False

		def dfs(curr, k, a):
			if curr > target:
				return False
			if curr == target:
				k -= 1
				curr = 0
			if not a:
				return True if not k else False
			for i in range(len(a)):
				if dfs(curr + a[i], k, a[:i] + a[i + 1:]):
					return True
		a.sort()
		target = sum(a) // k
		if a[-1] > target:
			return False
		while a and a[-1] == target:
			a.pop()
			k -= 1
		return dfs(0, k, a[::-1])


class Solution:

	def isKPartitionPossible(self, a, k):
		dp = [-1] * (1 << 12)
		dp[0] = 0
		n = len(a)
		summ = sum(a)
		if summ % k != 0:
			return False
		target = summ // k
		for mask in range(1 << n):
			if dp[mask] == -1:
				continue
			for i in range(n):
				if mask & 1 << i == 0 and dp[mask] + a[i] <= target:
					dp[mask | 1 << i] = dp[mask] + a[i]
					dp[mask | 1 << i] %= target
		return dp[(1 << n) - 1] == 0


class Solution:

	def isKPartitionPossible(self, a, k):
		if sum(a) % k != 0:
			return 0
		target = sum(a) // k
		vis = [False] * len(a)

		def recurse(i, l, k):
			if l == target:
				return recurse(0, 0, k - 1)
			if k == 0:
				return True
			for ind in range(i, len(a)):
				if vis[ind] == True:
					continue
				vis[ind] = True
				l += a[ind]
				if recurse(ind + 1, l, k) == True:
					return True
				l -= a[ind]
				vis[ind] = False
			return False
		return recurse(0, 0, k)


class Solution:

	def isKPartitionPossible(self, a, k):
		n = len(a)
		a.sort(reverse=True)
		Sum = sum(a)
		if Sum % k:
			return False
		used = [False] * n
		target = Sum // k

		def dfs(ind, total, k):
			if k == 0:
				return True
			if total == 0:
				return dfs(0, target, k - 1)
			for i in range(ind, n):
				if i > 0 and (not used[i - 1]) and (a[i - 1] == a[i]):
					continue
				if used[i] or total - a[i] < 0:
					continue
				used[i] = True
				if dfs(i + 1, total - a[i], k):
					return True
				used[i] = False
			return False
		return dfs(0, target, k)


class Solution:

	def isKPartitionPossible(self, nums, k):
		n = len(nums)
		nums.sort(reverse=True)
		total = sum(nums)
		if total % k != 0:
			return False
		target = int(total / k)
		used = [False] * n

		def dfs(index, total, k):
			if k == 0:
				return True
			if total == 0:
				return dfs(0, target, k - 1)
			for i in range(index, n):
				if i > 0 and (not used[i - 1]) and (nums[i] == nums[i - 1]):
					continue
				if used[i] or total - nums[i] < 0:
					continue
				used[i] = True
				if dfs(i + 1, total - nums[i], k):
					return True
				used[i] = False
			return False
		return dfs(0, target, k)


class Solution:

	def isKPartitionPossible(self, arr, k):
		n = len(arr)
		ans = [False]
		visited = [0] * n
		sum_arr = sum(arr)
		if k == 1:
			return True
		if sum_arr % k:
			return False
		target = sum_arr // k

		def rec(i, total, j):
			if not ans[0]:
				if total == target:
					if j == k - 1:
						ans[0] = True
					else:
						rec(0, 0, j + 1)
					return
				if i == n:
					return
				rec(i + 1, total, j)
				if not visited[i] and total + arr[i] <= target:
					visited[i] = 1
					rec(i + 1, total + arr[i], j)
					visited[i] = 0
		rec(0, 0, 1)
		return ans[0]


class Solution:

	def isKPartitionPossible(self, a, k):
		total = sum(a)
		if total % k != 0:
			return False
		share = total // k
		n = len(a)
		subset = [0] * n
		prev_choice = [-1] * n
		possible = False
		ind = 0
		sub = 1
		summation = 0
		prev = -1
		while True:
			if ind >= n:
				if prev == -1:
					break
				if subset[prev] != sub:
					sub = subset[prev]
					summation = share
				subset[prev] = 0
				summation -= a[prev]
				ind = prev + 1
				prev = prev_choice[prev]
			if ind < n and subset[ind] == 0:
				if a[ind] + summation <= share:
					prev_choice[ind] = prev
					summation += a[ind]
					subset[ind] = sub
					prev = ind
					ind += 1
					if summation == share:
						sub += 1
						if sub >= k:
							possible = True
							break
						ind = 0
						summation = 0
				else:
					ind += 1
			else:
				ind += 1
		return possible


class Solution:

	def find(self, i, a, d, gs, x, s):
		if x == 1:
			return True
		if gs == s:
			return self.find(0, a, d, 0, x - 1, s)
		for j in range(i, N):
			if not d[j]:
				d[j] = True
				if self.find(j + 1, a, d, gs + a[j], x, s):
					return True
				d[j] = False
		return False

	def isKPartitionPossible(self, a, k):
		d = [False] * N
		t = sum(a)
		if t % k != 0:
			return 0
		s = t // k
		return self.find(0, a, d, 0, k, s)


class Solution:

	def isKPartitionPossible(self, a, k):

		def solve(i, a, n, k, target, visit, cnt, cursum):
			if cursum == target:
				cursum = 0
				cnt += 1
				return solve(0, a, n, k, target, visit, cnt, cursum)
			if cnt == k + 1:
				return True
			if i >= n:
				return False
			if cursum > target:
				return False
			if visit[i] == 1:
				return solve(i + 1, a, n, k, target, visit, cnt, cursum)
			else:
				visit[i] = 1
				cursum += a[i]
				op1 = solve(i + 1, a, n, k, target, visit, cnt, cursum)
				visit[i] = 0
				cursum -= a[i]
				op2 = solve(i + 1, a, n, k, target, visit, cnt, cursum)
				return op1 or op2
		sum = 0
		n = len(a)
		for i in range(len(a)):
			sum += a[i]
		visit = [0] * n
		if sum % k != 0:
			return False
		if k == 1:
			return True
		if k >= n:
			return False
		target = sum // k
		return solve(0, a, n, k, target, visit, 1, 0)


class Solution:

	def isKPartitionPossible(self, a, k):
		if k == 1:
			return True
		if len(a) < k:
			return False
		if sum(a) % k != 0:
			return False
		sum_num = sum(a) // k
		used = [0] * len(a)
		self.res = False

		def dfs(index, cur, depth):
			if depth == k:
				return True
			if cur == sum_num:
				return dfs(0, 0, depth + 1)
			for i in range(index, len(a)):
				if used[i] or cur + a[i] > sum_num:
					continue
				used[i] = True
				res = dfs(index + 1, cur + a[i], depth)
				if res:
					return True
				else:
					used[i] = False
		return dfs(0, 0, 0)


class Solution:

	def is_possible(self, idx, res, subset_sums, a, k):
		if idx == len(a):
			if k == 0:
				for i in range(len(subset_sums) - 1):
					if subset_sums[i] != subset_sums[i + 1]:
						return False
				return True
			return False
		for i in range(len(res)):
			if len(res[i]) > 0:
				res[i].append(a[idx])
				subset_sums[i] += a[idx]
				if self.is_possible(idx + 1, res, subset_sums, a, k):
					return True
				res[i].pop()
				subset_sums[i] -= a[idx]
			else:
				res[i].append(a[idx])
				subset_sums[i] += a[idx]
				if self.is_possible(idx + 1, res, subset_sums, a, k - 1):
					return True
				res[i].pop()
				subset_sums[i] -= a[idx]
				break
		return False

	def isKPartitionPossible(self, a, k):
		s = 0
		for val in a:
			s += val
		if k > len(a) and s % k != 0:
			return False
		res = [[] for _ in range(k)]
		subset_sums = [0] * k
		return self.is_possible(0, res, subset_sums, a, k)


class Solution:

	def isKPartitionPossible(self, a, k):
		arr = [[] for i in range(k)]
		n = len(a)
		fill = 0
		ans = [0]
		if k == 1:
			return True

		def sol(i, fill, n):
			if i == n:
				if fill == k:
					s = sum(arr[0])
					for j in arr:
						if s != sum(j):
							return
					ans[0] += 1
					return
				else:
					return
			for j in range(k):
				if arr[j] == []:
					arr[j].append(a[i])
					sol(i + 1, fill + 1, n)
					arr[j].pop()
					return
				else:
					arr[j].append(a[i])
					sol(i + 1, fill, n)
					arr[j].pop()
		sol(0, 0, n)
		return ans[0]


class Solution:

	def isKPartitionPossible(self, array, k):
		i = 0
		n = len(array)
		zeroscount = 0
		holdanswer = [0 for i in range(k)]
		hold = self.solve(i, zeroscount, array, holdanswer, k, n)
		return hold

	def isPossible(self, result, k):
		hold = result[0]
		for value in result:
			if hold != value:
				return False
		return True

	def solve(self, i, zeroscount, array, holdanswer, k, n):
		if i >= n:
			if zeroscount == k:
				if self.isPossible(holdanswer, k):
					return True
			return False
		for j in range(len(holdanswer)):
			temp = array[i]
			if holdanswer[j] > 0:
				holdanswer[j] += temp
				if self.solve(i + 1, zeroscount, array, holdanswer, k, n):
					return True
				holdanswer[j] -= temp
			else:
				holdanswer[j] += temp
				if self.solve(i + 1, zeroscount + 1, array, holdanswer, k, n):
					return True
				holdanswer[j] -= temp
				break
		return False


class Solution:

	def isKPartitionPossible(self, array, k):
		self.result = list()
		i = 0
		n = len(array)
		zeroscount = 0
		holdanswer = [0 for i in range(k)]
		self.solve(i, zeroscount, array, holdanswer, k, n)
		if self.isPossible(k):
			return 1
		return 0

	def isPossible(self, k):
		for listdata in self.result:
			times = 1
			hold = listdata[0]
			for value in listdata:
				if hold != value:
					break
			else:
				return True
		return False

	def solve(self, i, zeroscount, array, holdanswer, k, n):
		if i >= n:
			if zeroscount == k:
				holdanswercpy = holdanswer.copy()
				self.result.append(holdanswercpy)
			return None
		for j in range(len(holdanswer)):
			temp = array[i]
			if holdanswer[j] > 0:
				holdanswer[j] += temp
				self.solve(i + 1, zeroscount, array, holdanswer, k, n)
				holdanswer[j] -= temp
			else:
				holdanswer[j] += temp
				self.solve(i + 1, zeroscount + 1, array, holdanswer, k, n)
				holdanswer[j] -= temp
				break
		return None


class Solution:

	def isKPartitionPossible(self, a, k):
		n = len(a)
		visited = [False] * n
		target = sum(a) / k

		def backtrack(i, k, curr_sum):
			if k == 0:
				return True
			if curr_sum == target:
				return backtrack(0, k - 1, 0)
			for j in range(i, n):
				if visited[j] or curr_sum + a[j] > target:
					continue
				visited[j] = True
				if backtrack(j + 1, k, curr_sum + a[j]):
					return True
				visited[j] = False
			return False
		return backtrack(0, k, 0)


class Solution:

	def solve(self, a, k, sum1, index, visited, subset, reqsum):
		if subset == k:
			return True
		if sum1 == 0:
			return self.solve(a, k, reqsum, 0, visited, subset + 1, reqsum)
		if index == len(a):
			return False
		if sum1 >= a[index] and visited[index] == False:
			visited[index] = True
			if self.solve(a, k, sum1 - a[index], index + 1, visited, subset, reqsum) == True:
				return True
			visited[index] = False
		ans = self.solve(a, k, sum1, index + 1, visited, subset, reqsum)
		return ans

	def isKPartitionPossible(self, a, k):
		sum1 = sum(a)
		if sum1 % k != 0:
			return False
		index = 0
		sum1 = sum1 // k
		visited = [False for i in range(len(a))]
		subset = 0
		reqsum = sum1
		return self.solve(a, k, sum1, index, visited, subset, reqsum)


class Solution:

	def isKPartitionPossible(self, nums, K):
		T = sum(nums)
		if T % K:
			return False
		N = len(nums)
		T = T // K
		taken = [False] * N
		d = {}

		def helper(S, K, curr):
			if K == 0:
				return True
			if S > T:
				return False
			if d.get((S, curr), None) != None:
				return d[S, curr]
			if S == T:
				d[S, curr] = helper(0, K - 1, curr)
				return d[S, curr]
			for i in range(len(nums)):
				if not taken[i]:
					taken[i] = True
					temp = curr
					curr = curr | 1 << i
					if helper(S + nums[i], K, curr):
						d[S, curr] = True
						return d[S, curr]
					curr = temp
					taken[i] = False
			d[S, curr] = False
			return d[S, curr]
		ans = helper(0, K, 0)
		return ans