Возврат
Лучшее решение, которое я могу придумать (с точки зрения сложности времени), - это алгоритм возврата.
Это очень похоже на грубую силу. В худшем случае он имеет одинаковую временную сложность грубой силы. Но это немного лучше, потому что он проверяет комбинации только там, где это имеет смысл.
Теория
Мы используем рекурсивную функцию visit, чтобы исследовать дерево комбинаций.
Каждая комбинация представлена путем от root до одного листа.
Пока здесь ничто не отличается от грубой силы, верно?
Однако наша функция будет достаточно умна, чтобы прекратить исследовать ветку дерева, когда построенное частичное решение будет равно или больше целевого значения (в вашем случае - 13).
Эта небольшая вещь делает Backtraking лучше, чем грубая сила для некоторых входных данных.
В худшем случае обратный возврат будет медленным, как грубая сила.
Но есть проблема !
Спасибо @ MartinR за указание на то, что текущая идея не работает с отрицательными числами.
Например, учитывая этот массив [1, 1, 1, 1, 5, -1] и 4 в качестве целевого значения алгоритм m вернет [1, 1, 1, 1] как лучшее решение, не считая, что [5, -1] действительно лучше.
Управление отрицательными числами
Чтобы управлять отрицательными числами, я добавил следующую логику c.
Если целевое значение равно 0 или положительное , то входной массив сортируется в порядке по возрастанию (отрицательные числа будут поставлены первыми).
Так [1, 1, 1, 1, 5, -1] станет [-1, 1, 1, 1, 1, 5].
В противном случае, если цель отрицательна, входной массив будет отсортирован в порядке убывания.
Так [1, 1, 1, 1, 5, -1] станет [5, 1, 1, 1, 1, -1].
Кодирование 10
Решение Swift состоит из 4 частей
-
SolutionHasNotExceededTarget typealias ArrayWithSum struct - Функция
smallestSubset(of:whereSumIs:) - Функция
visit(solution:unusedElms:target:solutionHasNotExceededTarget:)
1. SolutionHasNotExceededTarget
Мне нужно закрытие, чтобы проверить, превысило ли текущее решение цель.
Это зависит от знака цели.
Если цель неотрицательный, чем входной массив сортируется в порядке возрастания, и тогда текущее решение никогда не должно быть больше цели.
С другой стороны, если цель отрицательна, массив сортируется в порядке убывания, а затем текущее решение никогда не должно быть меньше цели.
Итак, резюмируем, что в случае отрицательной цели это закрытие будет
$0 > $1
Это означает, что если сумма текущих решение больше, чем цель, это нормально, потому что (будучи отрицательной целью) мы могли бы найти отрицательные числа позже, когда мы go глубже в дереве.
В противном случае, если цель не отрицательна, закрытие будет
$0 < $1
Это определение типа такого замыкания.
typealias SolutionHasNotExceededTarget = (Int, Int) -> Bool
2. ArrayWithSum
Код должен будет вычислять сумму всех целых чисел в массиве много раз. Эта операция имеет временную сложность O (m), где m - длина массива. Я не хочу тратить время на вычисление одного и того же значения несколько раз, поэтому я определю оболочку для Array of Int для хранения суммы его элементов.
struct ArrayWithSum: Comparable {
static let empty = ArrayWithSum([])
let array: [Int]
let sum: Int
init(_ array: [Int]) {
self.array = array
self.sum = array.reduce(0, +)
}
private init(arrayWithSum: ArrayWithSum, elm: Int) {
self.array = arrayWithSum.array + [elm]
self.sum = arrayWithSum.sum + elm
}
func appending(elm: Int) -> ArrayWithSum {
return ArrayWithSum(arrayWithSum: self, elm: elm)
}
static func < (lhs: ArrayWithSum, rhs: ArrayWithSum) -> Bool {
lhs.array.count < rhs.array.count
}
}
Как вы можете видеть, оболочка соответствует Comparable, что позволяет легко сравнивать 2 решения при поиске лучшего.
3. smallestSubset(of:whereSumIs:)
Эта функция подготовит данные для функции vist.
func smallestSubset(of nums: [Int], whereSumIs target: Int) -> [Int]? {
let sorting: SolutionHasNotExceededTarget = target > 0
? { $0 < $1 }
: { $0 > $1 }
let sortedNums = nums.sorted(by: sorting)
return visit(solution: .empty,
unusedElms: sortedNums,
target: target,
solutionHasNotExceededTarget: sorting)?.array
}
Сортирует массив в порядке возрастания, если цель не отрицательна. И в порядке убывания, если цель отрицательная.
4. visit(solution:unusedElms:target:solutionHasNotExceededTarget:)
Наконец, функция visit, которая применяет логику возврата c, описанную ранее.
func visit(solution: ArrayWithSum,
unusedElms: [Int],
target: Int,
solutionHasNotExceededTarget: SolutionHasNotExceededTarget) -> ArrayWithSum? {
if solution.sum == target {
return solution
}
guard solutionHasNotExceededTarget(solution.sum, target) else {
return nil
}
return unusedElms
.enumerated()
.map { (offset, elm) in
var unusedElms = unusedElms
unusedElms.remove(at: offset)
return visit(solution: solution.appending(elm: elm),
unusedElms: unusedElms,
target: target,
solutionHasNotExceededTarget: solutionHasNotExceededTarget)
}
.compactMap { $0 }
.min()
}
Test
Давайте запустим несколько тестов
smallestSubset(of: [1, 9, 2, 5, 3, 10], whereSumIs: 13)
> [3, 10]
smallestSubset(of: [1, 1, 1, 1, 5, -1], whereSumIs: 4)
> [-1, 5]
smallestSubset(of: [-1, 2, 10, 1, -1, -3, 5, -15], whereSumIs: -5)
> [10, -15]
smallestSubset(of: [-50, 2, 10, 1, -1, -3, 5, -5], whereSumIs: -5)
> [-5]
smallestSubset(of: [10, 9, 9, 2], whereSumIs: 20)
> [2, 9, 9]
Пространственная сложность
В отношении памяти, в худшем случае у нас будет столько открытых рекурсивных вызовов, сколько и высоты дерева.
Высота трех равна число элементов во входном массиве, так что.
Кроме того, рекурсивному вызову rach необходимо пространство пропорционально длине входного массива, поэтому.
Сложность пространства = O (n) * O (n) = O (n ^ 2)
Где n - количество элементов в входной массив.
Сложность времени
Как уже говорилось ранее, в худшем случае функция будет проверять каждую возможную комбинацию. Другими словами, каждый узел дерева будет посещен.
Сложность времени: O (2 ^ n)
Где n - это число элементы во входном массиве.