1
# Runtime: 165 ms (Top 74.37%) | Memory: 13.8 MB (Top 95.72%)
2
class Solution:
3
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
4
        def dfs(idx, curr, cnt, limit):
5
            if cnt == k:
6
                return True
7
            if curr == limit:
8
                return dfs(0, 0, cnt + 1, limit)
9

10
            i = idx
11
            while i < len(nums):
12
                if visited[i] or nums[i] + curr > limit:
13
                    i += 1
14
                    continue
15
                visited[i] = True
16
                if dfs(i + 1, curr + nums[i], cnt, limit):
17
                    return True
18
                visited[i] = False
19

20
                while i + 1 < len(nums) and nums[i] == nums[i + 1]:  # pruning1
21
                    i += 1
22
                if curr == 0 or curr + nums[i] == limit:  # pruning2
23
                    return False
24
                i += 1
25
            return False
26

27
        if len(nums) < k or sum(nums) % k:
28
            return False
29
        numSum = sum(nums)
30

31
        for i in range(len(nums)):
32
            if nums[i] > numSum // k:
33
                return False
34

35
        visited = [False] * len(nums)
36
        return dfs(0, 0, 0, numSum // k)