分區陣列分成相同總和值的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）上循環，並且如果每個子集中的元素值的總和不匹配，則過濾掉該值。