## 题目描述：

LeetCode 698. Partition to K Equal Sum Subsets

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 <= k <= len(nums) <= 16`.
• `0 < nums[i] < 10000`.

## Python代码：

``````class Solution(object):
def canPartitionKSubsets(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
dmap = {}
def solve(nums, target, k):
if k == 1: return sum(nums) == target
key = (tuple(nums), k)
if key in dmap: return dmap[key]
size = len(nums)
ans = False
for x in range(1 << size):
sums = 0
rest = []
for y in range(size):
if (x >> y) & 1:  sums += nums[y]
else: rest.append(nums[y])
if sums == target and solve(rest, target, k - 1):
ans = True
break
dmap[key] = ans
return ans
sums = sum(nums)
if sums % k: return False
return solve(sorted(nums), sums / k, k)
``````

Pingbacks已关闭。