数组分解K个等和子数组

[编程题]数组分解K个等和子数组

热度指数：3 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给一个整数数组num，和一个正整数k，能否把数组num 切成k个子集，且各个子集的和相等。

请写出代码，返回bool 类型

输入描述:

一个整数数组num，和一个正整数k

输出描述:

返回true 或者 false ，bool类型

示例1

输入

[4, 3, 2, 3, 5, 2, 1];4

输出

True

说明

可以分解为四个，他们之和都是5： (5), (1, 4), (2,3), (2,3)

算法知识视频讲解

开挂了的菜鸡很想奋斗

发表于 2023-09-19 00:30:36

该题涉及的细节较多，采用的多种优化方法，具体可参见具体代码。同时该题的输入为一个字符串需要一定的字符串分割处理能力。该题的大致思路是将数组中的n个元素视为小球，小球有质量nums[i]。k个子集视为盒子，每个盒子必须装质量恰好为target的小球。对于每个盒子来说每个小球共有两种状态“装入”或“不装展开全文