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.

Difficulty: interview

Starter code:

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

Solutions:
class Solution:
     def canPartitionKSubsets(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """
         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
 #        print(answer)
     
     def dfs(self, visit, accu, k):
         if k == 1:
 #            print(visit)
             return True
         
         for i in range(len(self.nums)):
             if not visit[i]:
                 #print(visit)
                 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):
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """
         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):
         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):
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """
         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):
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """
         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):
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """
         
         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:
                     # this line is important, otherwise TLE.
                     # if subsets[i] is 0 then later subsets are all zeros. No need to try them all.
                     break
             nums.append(selected)
             return False
         
         return partition(nums, subsets=[0]*k, target=target)

class Solution:
     def canPartitionKSubsets(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """
         total = sum(nums)
         if total%k!=0:
             return False
         target = total/k
         
         used = [False]*len(nums)
         nums = sorted(nums)
         # print(nums)
         def check(nums, k, cur, pos):
             # print(used, 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:
     def canPartitionKSubsets(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """
         target, rem = divmod(sum(nums), k)
         if rem: return False
 
         def search(groups):
             if not nums: return True
             v = nums.pop()
             for i, group in enumerate(groups):
                 if group + v <= target:
                     groups[i] += v
                     if search(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:
             nums.pop()
             k -= 1
 
         return search([0] * k)

class Solution(object):
     def canPartitionKSubsets(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """
         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):
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """
         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):
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """
         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):
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """
         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