判断能否将非负整数数组划分为恰好K个和相等的非空子数组

给定一个大小为N的非负整数数组A，需要判断是否能将其恰好划分成K个非空子数组，且每个子数组的元素和相等。如果可行输出Yes，否则输出No。注意：数组中的每个元素必须恰好属于一个子数组。

示例 #

• 示例数组：[3,0,1,2,0,0,6,0,1,5]
• 示例输出：Yes
• 解释：可划分为三个子数组{3,0,1,2,0,0}、{6}、{0,1,5}，每个子数组的和均为6。

实现代码 #

listt = [3,0,1,2,0,0,6,0,1,5]
# listt.sort()
# listt = [i for i in listt if i != 0]

def find_next_sum(summ,listt,last_index,counter):
    if last_index == 0: #刚开始遍历数组
    # 尝试不同的起始子数组和
        for i in range(last_index,len(listt)-1):
            # 以0到i的元素和作为第一个目标和
            print("reset : last_index:",i+1,"sum:",sum(listt[0:i+1]))
            result = find_next_sum(sum(listt[0:i+1]),listt,i+1,1)
            print(result)
        # 若遍历完所有起始可能仍无结果，则无法划分
        
    else:
        # 已有目标和，寻找下一个和匹配的子数组
        for j in range(last_index,len(listt)):
            next_summ = sum(listt[last_index:j+1])
            print("current_sum:",summ,"next_sum:",next_summ,"last_index:",last_index,"end_index:",j+1)

            if summ == next_summ:
                if j+1 == len(listt):
                    # 到达数组末尾且和匹配，返回成功
                    return 'Yes'
                if j+1 < len(listt):
                    # 继续寻找下一个符合条件的子数组
                    find_next_sum(next_summ,listt,j+1,counter+1)                

            elif summ != next_summ:
                if next_summ < summ and j+1 < len(listt): 
                    # 当前和未达到目标，继续扩展子数组
                    continue
                if j+1 == len(listt):
                    # 到达末尾仍未匹配，返回失败
                    return 'No'
            # 跳出循环，尝试其他起始子数组
            break

find_next_sum(0,listt,0,0)

内容的提问来源于stack exchange，提问作者Palash