# 698. Partition to K Equal Sum Subsets 划分为k个相等的子集

@TOC

## # 题目描述

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

## # 解题方法

### # 回溯法

Python代码：

``````class Solution:
def canPartitionKSubsets(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
if not nums or len(nums) < k: return False
_sum = sum(nums)
div, mod = divmod(_sum, k)
if _sum % k or max(nums) > _sum / k: return False
nums.sort(reverse = True)
target = [div] * k
return self.dfs(nums, k, 0, target)

def dfs(self, nums, k, index, target):
if index == len(nums): return True
num = nums[index]
for i in range(k):
if target[i] >= num:
target[i] -= num
if self.dfs(nums, k, index + 1, target): return True
target[i] += num
return False
``````

C++代码如下：

``````class Solution {
public:
bool canPartitionKSubsets(vector<int>& nums, int k) {
if (nums.size() < k) return false;
int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum % k != 0) return false;
vector<int> target(k, sum / k);
return helper(nums, 0, target);
}

bool helper(vector<int>& nums, int index, vector<int>& target) {
if (index == nums.size()) return true;
int num = nums[index];
for (int i = 0; i < target.size(); ++i) {
if (target[i] >= num) {
target[i] -= num;
if (helper(nums, index + 1, target))
return true;
target[i] += num;
}
}
return false;
}
};
``````

``````class Solution(object):
def canPartitionKSubsets(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
if k == 1: return True
self.n = len(nums)
if self.n < k: return False
total = sum(nums)
if total % k: return False
self.target = total / k
visited = [0] * self.n
nums.sort(reverse = True)
def dfs(k, ind, sum, cnt):
if k == 1: return True
if sum == self.target and cnt > 0:
return dfs(k - 1, 0, 0, 0)
for i in range(ind, self.n):
if not visited[i] and sum + nums[i] <= self.target:
visited[i] = 1
if dfs(k, i + 1, sum + nums[i], cnt + 1):
return True
visited[i] = 0
return False
return dfs(k, 0, 0, 0)
``````

## # 日期

2018 年 4 月 2 日 —— 要开始准备ACM了 2019 年 2 月 24 日 —— 周末又结束了