递归-数组划分为K个相等子集

# 给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

# 示例 1：
# 输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
# 输出： True
# 说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。

nums = list(map(int, input().split(',')))
k = int(input())


def getResult(nums, k):
    total = sum(nums)
    s_nums = sorted(nums)
    if total % k != 0:
        return False
    everage = total // k
    if s_nums[-1] > everage:
        return False
    
    arr = [everage] * k
    pos = len(nums) - 1
    
    return dfs(s_nums, pos, arr, k)

def dfs(nums, pos, arr, k):
    if pos < 0:
        return True
    for i in range(k):
        if i > 0 and arr[i] == arr[i-1]:
            continue
        if arr[i] ==nums[pos] or (pos > 0 and arr[i] - nums[pos] >= nums[0]):
            arr[i] -= nums[pos]
            if dfs(nums, pos - 1, arr, k):
                return True
            arr[i] += nums[pos]

    return False

print(getResult(nums, k))