LC698 Partition to K Equal Sum Subsets

# time O(K*2^N) 
class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        if k <2 :
            return True
        size = len(nums)
        if size < k:
            return False
        target = sum(nums)/k
        visited = [0]* size
        return self.dfs(0,nums,visited,0,k,target)
            
    def dfs(self, start, nums, visited, sum, k, target):
        if k == 1:
                return True
        if sum == target:
            return self.dfs(0,nums,visited,0,k-1,target)
        for i in range(start,len(nums)):
            # to optimize
            if sum > target or nums[i]>target:
                return False
            if visited[i] == 0:
                visited[i] = 1
                if self.dfs(i+1,nums,visited,sum+nums[i],k,target):
                    return True
                visited[i] = 0
        return False