52. Combination Sum

読了目安約2分

Greedy / Backtracking / LeetCode 39 (Medium) — 同じ数を何度も使って和を target にする組合せ

この章の目次

問題

LeetCode 39. Combination Sum（Medium / カテゴリ: Greedy / Backtracking）

相異なる正の整数の配列 candidates と整数 target が与えられます。和がちょうど target になる組合せをすべて返す問題です。同じ数は何度でも使えますが、並び順だけ違う組合せを 2 回返してはいけません。

返す順序は自由です。このページのテストコードは、結果をソートしてから期待値と比較します。

考え方

ヒント 1

51. Subsets と同じバックトラッキングです。「残りいくら必要か」を引数 remaining で渡し、0 になったら 1 組完成です。

ヒント 2

並び順だけ違う組合せを防ぐには、backtrack(start, remaining) で「start 番目より前の候補は使わない」と決めます。同じ数を繰り返し使えるように、候補 i を選んだ後の再帰には i + 1 ではなく i を渡します。

Swift 実装のポイント

51 と同じく、ネスト関数と append / removeLast() の組で書けます。
再帰に渡す開始位置を i のままにするのがこの問題の肝です。i + 1 にすると各候補が 1 回しか使えなくなります。
candidates[i] > remaining の候補は足すと超えるだけなので、スキップして枝を刈ります。

模範解答

Swift
class Solution {
    func combinationSum(_ candidates: [Int], _ target: Int) -> [[Int]] {
        var result: [[Int]] = []
        var current: [Int] = []
        func backtrack(_ start: Int, _ remaining: Int) {
            if remaining == 0 {
                result.append(current)
                return
            }
            for i in start..<candidates.count {
                if candidates[i] > remaining { continue }
                current.append(candidates[i])
                backtrack(i, remaining - candidates[i])
                current.removeLast()
            }
        }
        backtrack(0, target)
        return result
    }
}

計算量: O(n^(T/M))（T は target、M は最小の候補）。