Это вариант задачи о подмножестве сумм , или, в более общем случае, задачи о ранце .Следующее решение предполагает, что:
- Все элементы исходного массива строго положительны,
- Исходный массив может содержать повторяющиеся элементы,
- Если сумма может 'После этого мы получим пустой массив.
Начнем с примера: давайте создадим динамическую таблицу 1016 *, в которой мы попытаемся найти все способы получения5 путем добавления элементов из [1, 2, 3, 4]:
В этой таблице строки представляют элементы массива в порядке возрастания,плюс 0.Столбцы переходят от 0 к сумме 5.
В каждой ячейке, мы спрашиваем себя, можем ли мы добраться до заголовка этого столбца, добавив один или несколько заголовков текущего ипредыдущие строки.
Количество решений - это количество ячеек, содержащих true.В этом случае два решения:
1)
Зеленая ячейка - true,поэтому текущая строка является последним элементом решения.В этом случае 3 является частью решения.Таким образом, проблема поиска подмассива, сумма которого равна 5, становится нахождением подмассива, сумма которого равна 5 - 3.Что 2.Это обозначено фиолетовым arrow 1: идите пять столбцов влево и 1 ряд вверх.
В arrow 2 мы ищем подмножество, которое позволило получить частичную сумму 2.В этом случае мы получаем два благодаря элементу 2.Таким образом, следуя arrow 2, мы идем на одну строку вверх, а две влево.
С помощью arrow 3 мы достигаем первой ячейки в первом столбце, соответствующей 5 - 3 - 2, что составляет 0.
2)
Другой путь, который мы могли бы выбрать, начинается с красной ячейки:
Как видите, проблема получения 5 из [1, 2, 3, 4] становится новой меньшей проблемой: 1 из [1, 2, 3], затем 1 из [1, 2] и, наконец, 1 из ` 1.
Давайте создадим и заполним динамическую таблицу:
var dynamicTable: [[Bool]] =
Array(repeating: Array(repeating: false, count: sum + 1),
count: array.count + 1)
//All of the elements of the first column are true
//since we can always make a zero sum out of not elements
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]) {
//The following block will be executed when
//we reach the first cell in the first column
if row == 0,
currentSum == 0
{
solutions.append(currentSolution)
//notice the return to exit the scope
return
}
//The following block will be executed if
//the current cell is NOT used to reach the sum
if dynamicTable[row - 1][currentSum]
{
getSubArraysWithTheSum(arr: arr,
row: row - 1,
currentSum: currentSum,
currentSolution: currentSolution)
}
//The following block will be executed if
//the current cell IS used to reach the sum
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)
//All of the elements of the first column are true
//since we can always make a zero sum out of not elements
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]) {
//The following block will be executed when
//we reach the first cell in the first column
if row == 0,
currentSum == 0
{
solutions.append(currentSolution)
return
}
//The following block will be executed if
//the current cell is NOT used to reach the sum
if dynamicTable[row - 1][currentSum]
{
getSubArraysWithTheSum(arr: arr,
row: row - 1,
currentSum: currentSum,
currentSolution: currentSolution)
}
//The following block will be executed if
//the current cell IS used to reach the sum
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 * Вклад 1099 * здесь .Подробное объяснение того, как создается динамическая таблица, можно найти в этом видео .