这是子集和问题的一种变体，或者更一般地说，是
背包问题。以下解决方案假设：
- 初始数组的所有元素均为严格正数，
- 初始数组可能包含重复元素，
- 如果无法达到总和，则输出为空数组。
让我们以一个例子开始：我们创建一个
动态表，在其中尝试通过从
[1, 2, 3, 4]中添加元素来找到获得
5的所有方法：
在这个表格中，行代表数组的元素，按升序排列，加上
0。列从
0到总和
5。
在每个单元格中，我们问自己，通过添加当前和前几行的标题中的一个或多个，我们能否到达此列的标题。
解决方案的数量是在其中具有
true的单元格的计数。在这种情况下，有两个解决方案：
1)
绿色的单元格是
true，因此当前行是解决方案的最后一个元素。在这种情况下，
3 是解的一部分。因此，找到子数组的和为5的问题，变成了找到子数组的和为
5-3的问题。这是
2。这由紫色
箭头1表示：向左移动五列，向上移动一行。
在
箭头2中，我们寻找使部分和为
2的子集。在这种情况下，我们得到了两个，归功于
2元素。因此，遵循
箭头2，我们向上移动一行，向左移动两个位置。
使用
箭头3，我们到达第一列的第一个单元格，对应于
5 - 3 - 2，即
0。
2)
我们可以从红色单元格开始另一条路径：
正如您所看到的，将
[1、2、3、4]中取出5个元素的问题，变成了从
[1、2、3]中取出1个元素的小问题，然后是从
[1、2]中取出1个元素，最后是从`
1`中取出1个元素的问题。
让我们创建并填充动态表格：
var dynamicTable: [[Bool]] =
Array(repeating: Array(repeating: false, count: sum + 1),
count: array.count + 1)
for i in 0...array.count {
dynamicTable[i][0] = true
}
for row in 1...array.count {
for column in 1...sum {
if column < array[row - 1] {
dynamicTable[row][column] = dynamicTable[row - 1][column]
} else {
if dynamicTable[row - 1][column] {
dynamicTable[row][column] = true
} else {
dynamicTable[row][column] = dynamicTable[row - 1][column - array[row - 1]]
}
}
}
}
让我们找到所有通往总和的路径：
var solutions = [[Int]]()
func getSubArraysWithTheSum(arr: [Int], row: Int, currentSum: Int, currentSolution: [Int]) {
if row == 0,
currentSum == 0
{
solutions.append(currentSolution)
return
}
if dynamicTable[row - 1][currentSum]
{
getSubArraysWithTheSum(arr: arr,
row: row - 1,
currentSum: currentSum,
currentSolution: currentSolution)
}
if currentSum >= arr[row - 1],
dynamicTable[row - 1][currentSum - arr[row - 1]]
{
getSubArraysWithTheSum(arr: arr,
row: row - 1,
currentSum: currentSum - arr[row - 1],
currentSolution: currentSolution + [arr[row - 1]])
}
}
整个函数看起来像这样：
func getSubArrays(from array: [Int], withSum sum: Int) -> [[Int]] {
guard array.allSatisfy({ $0 > 0 }) else {
fatalError("All the elements of the array must be strictly positive")
}
guard array.count > 0, sum > 0 else {
return []
}
var solutions = [[Int]]()
var dynamicTable: [[Bool]] =
Array(repeating: Array(repeating: false, count: sum + 1),
count: array.count + 1)
for i in 0...array.count {
dynamicTable[i][0] = true
}
for row in 1...array.count {
for column in 1...sum {
if column < array[row - 1] {
dynamicTable[row][column] = dynamicTable[row - 1][column]
} else {
if dynamicTable[row - 1][column] {
dynamicTable[row][column] = true
} else {
dynamicTable[row][column] = dynamicTable[row - 1][column - array[row - 1]]
}
}
}
}
func getSubArraysWithTheSum(arr: [Int], row: Int, currentSum: Int, currentSolution: [Int]) {
if row == 0,
currentSum == 0
{
solutions.append(currentSolution)
return
}
if dynamicTable[row - 1][currentSum]
{
getSubArraysWithTheSum(arr: arr,
row: row - 1,
currentSum: currentSum,
currentSolution: currentSolution)
}
if currentSum >= arr[row - 1],
dynamicTable[row - 1][currentSum - arr[row - 1]]
{
getSubArraysWithTheSum(arr: arr,
row: row - 1,
currentSum: currentSum - arr[row - 1],
currentSolution: currentSolution + [arr[row - 1]])
}
}
getSubArraysWithTheSum(arr: array, row: array.count , currentSum: sum, currentSolution: [])
return solutions
}
以下是一些测试用例：
getSubArrays(from: [3, 1, 4, 2], withSum: 5) //[[3, 2], [4, 1]]
getSubArrays(from: [1, 2, 2, 4], withSum: 3) //[[2, 1], [2, 1]]
getSubArrays(from: [7, 3, 4, 5, 6, 1], withSum: 9) //[[5, 3, 1], [5, 4], [6, 3]]
getSubArrays(from: [3], withSum: 3) //[[3]]
getSubArrays(from: [5], withSum: 10) //[]
getSubArrays(from: [1, 2], withSum: 0) //[]
getSubArrays(from: [], withSum: 4) //[]
这个解决方案是受到了Sumit Ghosh的贡献的启发，
此处。如何构建动态表格的详细解释可以在
这个视频中找到。
- 所有元素都是正数。
- 数组的元素可能重复。
- 如果出现零，空数组可以作为答案。
- Adeel Miraj