分区阵列分成相同总和值的K个子集

Question

试图找出下列问题：

给定N个正整数的集合S的任务是把它们分为K个子集，使得元件值的总和在每个K子集中都是相等的。

我想用一组不超过10个整数的值来做到这一点，值不大于10，并且少于5个子集。 所有整数需要进行分配，只有完美的解决方案（这意味着所有子集都是平等的，没有近似）被接受。 我希望它使用递归回溯解决。我在网上发现的大多数资源都是使用其他我不明白的方法，使用位掩码或其他方法，或者仅用于两个子集而不是K子集。

我的第一个想法是

1. 排序集合按升序顺序，检查所有的基础情况下（例如均匀分布是不可能的），计算平均值所有子集要有使所有子集等于。
2. 通过每个子集，填充每个子集（从最大值开始），直到达到平均值（意味着它们已满）。
3. 如果子集的平均值不能满足（未分配值太大等），返回并尝试其他子集的其他组合。
4. 保持如果遇到死角回去。如果已经遇到的所有死角
5. 停止或完美的解决方案被发现。

不幸的是，我真的很困难，尤其是在实施回溯和重新组合新方案时。

任何帮助表示赞赏！

Answer 1

给定的集合：S有N个元素有2^N个子集。 （阱这里解释：https://www.mathsisfun.com/activity/subsets.html）分区是是一组的元素的分组到非空子集，以这样的方式，每一个元件被包括在一个和仅一个子集。 n元素集合的总数partitions是贝尔数Bn。

1）创建集合S的所有可能partitions，称为P（S）：

针对此问题的解决方案可以如下来实现。 2）在P（S）上循环，并且如果每个子集中的元素值的总和不匹配，则过滤掉该值。