划分等和序列

# -*- coding: utf-8 -*-

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param nums int整型一维数组
# @param k int整型
# @return bool布尔型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/89ceab10d36140ce8f0d38c56e417f02?tpId=196&tqId=40516&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=
    算法：
        1. 边界考虑：
            设nums的长度为n，所有元素和为sum，最大值为maxNum，target = sum / k
            a）如果n < k，无法分割，返回False
            b）如果sum % k != 0，无法分割，返回False
            c) 如果maxNum > target，无法分割，返回False
        2. 回溯函数dfs(k, target)表示当前剩余分割的序列数为k，当前分割区间剩余匹配的目标值为target
            若k == 0，说明分割成功，返回True
            若target == 0，需要分割的区间数-1，继续递归
            枚举当前可选的有效元素，标记为已访问，继续递归；回溯
    复杂度：
        时间复杂度：？？？
        空间复杂度：O(n)
    """

    def candivide(self, nums, k):
        # write code here
        def dfs(k, remain):
            if k == 0: # 分割序列成功
                return True
            if remain == 0: #
                if dfs(k - 1, target):
                    return True
            for i in range(n):
                if nums[i] > remain&nbs***bsp;visited[i]:  # 当前元素大于剩余匹配值 或者 已被选取
                    continue
                visited[i] = True
                if dfs(k, remain - nums[i]):
                    return True
                visited[i] = False
            return False

        n, Sum = len(nums), sum(nums)
        if n < k&nbs***bsp;Sum % k != 0:
            return False

        nums.sort(reverse=True)
        target = Sum / k
        if nums[0] > target:
            return False

        visited = [False] * n

        return dfs(k, target)


if __name__ == "__main__":
    sol = Solution()

    # nums, k = [5, 1, 3, 2, 4], 3

    nums, k = [5, 1, 4, 2, 3, 2], 3

    res = sol.candivide(nums, k)

    print res