Given an array of integers nums and a positive integer k, find whether it's possible to divide this array into k non-empty subsets whose sums are all equal.

Example 1:

Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
Output: True
Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.



Note:
1 .
0 < nums[i] < 10000.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Bit manipulation

Data structures

Complete search

Starter code: class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        

Solutions:
class Solution:

	def canPartitionKSubsets(self, nums, k):
		(target, rem) = divmod(sum(nums), k)
		if rem or max(nums) > target:
			return False
		n = len(nums)
		seen = [0] * n
		nums.sort(reverse=True)

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


class Solution:

	def canPartitionKSubsets(self, nums, k):
		quotient = sum(nums) / k
		if quotient % 1 != 0:
			return False
		for num in nums:
			if num > quotient:
				return False
			if num == quotient:
				nums.remove(quotient)
				k -= 1
		nums.sort(reverse=True)
		self.nums = nums
		self.quotient = quotient
		print(self.nums)
		answer = self.dfs([0] * len(nums), 0, k)
		return answer

	def dfs(self, visit, accu, k):
		if k == 1:
			return True
		for i in range(len(self.nums)):
			if not visit[i]:
				if self.nums[i] + accu < self.quotient:
					visit[i] = 1
					if self.dfs(visit, self.nums[i] + accu, k):
						return True
					visit[i] = 0
				if self.nums[i] + accu == self.quotient:
					visit[i] = 1
					accu = self.nums[i] + accu
					return self.dfs(visit, 0, k - 1)
		return False


class Solution:

	def partition(self, nums, target, current, pos, fill):
		if fill == 0:
			return True
		for i in range(pos, len(nums)):
			next = nums[:i] + nums[i + 1:]
			if current + nums[i] == target:
				if self.partition(next, target, 0, 0, fill - 1):
					return True
			elif current + nums[i] < target:
				if self.partition(next, target, current + nums[i], i, fill):
					return True
			elif current == 0:
				return False
		return False

	def canPartitionKSubsets(self, nums, k):
		s = sum(nums)
		if s % k > 0:
			return False
		target = s // k
		return self.partition(nums, target, 0, 0, k)


class Solution:

	def canPartitionKSubsets(self, nums, k):
		if sum(nums) % k or len(nums) < k:
			return False
		if k == 1:
			return True
		(target, used) = (sum(nums) / k, [False for i in range(len(nums))])

		def dfs(start, sum_, k):
			if k == 1:
				return True
			if sum_ == target:
				return dfs(0, 0, k - 1)
			for i in range(start, len(nums)):
				if not used[i] and sum_ < target:
					used[i] = True
					if dfs(i + 1, sum_ + nums[i], k):
						return True
					used[i] = False
			return False
		return dfs(0, 0, k)


class Solution:

	def canPartitionKSubsets(self, nums, k):
		(target, rem) = divmod(sum(nums), k)
		if rem:
			return False

		def dfs(groups):
			if not nums:
				return True
			v = nums.pop()
			for (i, group) in enumerate(groups):
				if group + v <= target:
					groups[i] += v
					if dfs(groups):
						return True
					groups[i] -= v
				if not group:
					break
			nums.append(v)
			return False
		nums.sort()
		if nums[-1] > target:
			return False
		while nums and nums[-1] == target:
			k -= 1
			nums.pop()
		return dfs([0] * k)


class Solution:

	def canPartitionKSubsets(self, nums, k):
		total = sum(nums)
		if total % k != 0:
			return False
		target = total // k
		nums.sort()
		if nums[-1] > target:
			return False
		while nums and nums[-1] == target:
			nums.pop()
			k -= 1
		return self.helper(nums, target, [0] * k)

	def helper(self, nums, target, dp):
		if not nums:
			return True
		num = nums.pop()
		for i in range(len(dp)):
			if dp[i] + num <= target:
				dp[i] += num
				if self.helper(nums, target, dp):
					return True
				dp[i] -= num
			if dp[i] == 0:
				break
		nums.append(num)
		return False


class Solution:

	def canPartitionKSubsets(self, nums, k):
		if not nums:
			return True
		if sum(nums) % k != 0:
			return False
		target = sum(nums) / k
		nums.sort()
		if nums[-1] > target:
			return False
		while nums and nums[-1] == target:
			nums.pop()
			k -= 1

		def partition(nums, subsets, target):
			if not nums:
				return True
			selected = nums.pop()
			for i in range(len(subsets)):
				if subsets[i] + selected <= target:
					subsets[i] += selected
					if partition(nums, subsets, target):
						return True
					subsets[i] -= selected
				if subsets[i] == 0:
					break
			nums.append(selected)
			return False
		return partition(nums, subsets=[0] * k, target=target)


class Solution:

	def canPartitionKSubsets(self, nums, k):
		total = sum(nums)
		if total % k != 0:
			return False
		target = total / k
		used = [False] * len(nums)
		nums = sorted(nums)

		def check(nums, k, cur, pos):
			if k == 1:
				return True
			for i in range(pos, -1, -1):
				if not used[i]:
					if nums[i] + cur < target:
						used[i] = True
						if check(nums, k, cur + nums[i], i - 1):
							return True
						used[i] = False
					elif nums[i] + cur == target:
						used[i] = True
						if check(nums, k - 1, 0, len(nums) - 1):
							return True
						used[i] = False
			return False
		return check(nums, k, 0, len(nums) - 1)


class Solution(object):

	def canPartitionKSubsets(self, nums, k):
		he = sum(nums)
		if he % k != 0:
			return False
		target = he // k
		visit = [0 for _ in range(len(nums))]

		def dfs(k, ind, cur, cnt):
			if k == 0:
				return True
			if cur == target and cnt > 0:
				return dfs(k - 1, 0, 0, 0)
			for i in range(ind, len(nums)):
				if not visit[i] and cur + nums[i] <= target:
					visit[i] = 1
					if dfs(k, i + 1, cur + nums[i], cnt + 1):
						return True
					visit[i] = 0
			return False
		return dfs(k, 0, 0, 0)


class Solution:

	def canPartitionKSubsets(self, nums, k):
		total = sum(nums)
		if total % k != 0:
			return False
		subsetTotal = total // k
		visited = [0] * len(nums)
		return self.helper(k, 0, 0, visited, nums, k, subsetTotal)

	def helper(self, remainingSets, index, s, visited, nums, k, subsetTotal):
		if remainingSets == 1:
			return True
		if s == subsetTotal:
			return self.helper(remainingSets - 1, 0, 0, visited, nums, k, subsetTotal)
		for i in range(index, len(nums)):
			if visited[i] == 0 and s + nums[i] <= subsetTotal:
				visited[i] = 1
				if self.helper(remainingSets, i + 1, s + nums[i], visited, nums, k, subsetTotal):
					return True
				visited[i] = 0
		return False


class Solution:

	def canPartitionKSubsets(self, nums, k):
		tot = sum(nums)
		if k <= 0 or tot % k != 0:
			return False
		visited = [0] * len(nums)

		def canPart(nums, visited, idx, curSum, k, target):
			if k == 1:
				return True
			if curSum == target:
				return canPart(nums, visited, 0, 0, k - 1, target)
			if curSum > target:
				return False
			for i in range(idx, len(nums)):
				if not visited[i]:
					visited[i] = 1
					if canPart(nums, visited, i + 1, curSum + nums[i], k, target):
						return True
					visited[i] = 0
			return False
		return canPart(nums, visited, 0, 0, k, tot / k)


class Solution:

	def canPartitionKSubsets(self, nums, k):
		if k <= 0:
			return False
		nums_sum = sum(nums)
		if nums_sum % k != 0:
			return False
		visited = [False] * len(nums)
		nums.sort(reverse=True)
		return self.canPartition(nums, visited, k, 0, 0, nums_sum / k)

	def canPartition(self, nums, visited, k, currentIndex, currentSum, target):
		if k == 1:
			return True
		if currentSum == target:
			return self.canPartition(nums, visited, k - 1, 0, 0, target)
		for i in range(currentIndex, len(nums)):
			if visited[i] is False and currentSum + nums[i] <= target:
				visited[i] = True
				if self.canPartition(nums, visited, k, i + 1, currentSum + nums[i], target):
					return True
				visited[i] = False
		return False