Смена монет в Swift с печатью всех комбинаций

Question

Я хочу расширить свой код для определения количества комбинаций, в которых данный набор монет может достичь заданной суммы, чтобы напечатать различные комбинации, которые суммируются на эту сумму.

У меня есть работающее решение для запоминанияк простой проблеме смены монет, которая обеспечивает способы получения суммы, например,

ways(n: 4, coins: [1,2,3])

дает 4.

func ways(n: Int, coins: [Int]) -> Int {
    var memo: [[Int]] = Array(repeating: Array(repeating: 0, count: coins.count), count: n)
    return coinChange(n, coins, 0, 0, &memo)
}

// cache is a concatenation of amount - index
func coinChange(_ target: Int, _ coins: [Int], _ ptr: Int, _ current : Int, _ memo: inout [[Int]])  -> Int {
    if (current == target) { return 1 }
    if (ptr > coins.count - 1) {return 0}
    if (current > target) {return 0}
    var sum = 0
    if (memo[current][ptr] != 0) {
        return memo[current][ptr]
    }

    // add the current coin and don't move on
    sum += coinChange(target, coins, ptr, current + coins[ptr], &memo )
    // don't take the current coin, and therefore more on
    sum += coinChange(target, coins, ptr + 1, current, &memo)
    memo[current][ptr] = sum
    return sum

}

Я понимаю, что естьСуществуют разные подходы DP к приведенному выше коду, но этот вопрос касается печати способов, а не относительно подхода, принятого выше.

Однако я изо всех сил пытаюсь вернуть способы, которыми мы достигаем различную комбинацию достижения 4.Чтобы быть понятным, 4 пути [[1,1,1,1], [2,2], [1,1,2],] [1,3]].

Я понимаю этобудет связан с печатью таблицы заметок, но я не могу представить, как это должно работать, и я не близок к ответу.