Partition to K Equal Sum Subsets

https://leetcode.com/problems/partition-to-k-equal-sum-subsets/description/

https://leetcode.com/problems/partition-equal-subset-sum/description/

When we want to partition an array into many sets .....

1. sum of every set have to be total_sum/k
2. pick a start position and do DFS for each iteration

class Solution(object):
    def canPartitionKSubsets(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """

        sum = 0
        target = 0
        visited = [0]*len(nums)

        for num in nums:
            sum += num

        if sum % k != 0:
            return False
        target = sum / k

        def canPartition(k, start, cur_sum, cnt, target, visited, nums):
            if k == 1:
                return True

            if cnt > 0 and target == cur_sum:
                return canPartition(k-1, 0, 0, 0, target, visited, nums)

            for i in range(start, len(nums)):
                if visited[i] == 0 and cur_sum + nums[i] <= target:
                    visited[i] = 1
                    if canPartition(k, i+1, cur_sum + nums[i], cnt + 1, target, visited, nums):
                        return True
                    visited[i] = 0

            return False

        return canPartition(k, 0, 0, 0, target, visited, nums)