题目描述：

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.

题目大意：

判断数组nums是否可以划分为k个和相等的子数组

解题思路：

记忆化搜索（Search + Memoization）

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)

 

本文链接：http://bookshadow.com/weblog/2017/10/15/leetcode-partition-to-k-equal-sum-subsets/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码