51. Subsets

読了目安約2分

Greedy / Backtracking / LeetCode 78 (Medium) — すべての部分集合を列挙する

この章の目次

問題

LeetCode 78. Subsets（Medium / カテゴリ: Greedy / Backtracking）

相異なる整数の配列 nums の部分集合をすべて返す問題です。空集合と nums 全体も含めます。要素数は最大 10 なので、部分集合は最大で 2^10 = 1024 個です。

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

考え方

ヒント 1

各要素について「入れる」か「入れない」かを決めると、部分集合が 1 つ決まります。 n 要素なら 2^n 通りです。

ヒント 2

候補を 1 つ選んで再帰し、戻ってきたら選択を取り消して次の候補を試す書き方をバックトラッキングと呼びます。作りかけの部分集合を 1 本の配列 current に持ち、再帰のたびにまず current を答えに記録します。 backtrack(start) を「start 番目以降の要素だけを追加してよい」と決めると、同じ部分集合が 2 回できません。

Swift 実装のポイント

再帰関数はメソッドの中にネストして書けます。result と current を引数で引き回さずに済みます。
current.append(...) したら、再帰から戻った直後に removeLast() で元に戻します。この対称が崩れるとバグになります。
配列は値型なので、result.append(current) の時点で中身がコピーされます。後から current を変えても記録済みの答えは変わりません。

模範解答

Swift
class Solution {
    func subsets(_ nums: [Int]) -> [[Int]] {
        var result: [[Int]] = []
        var current: [Int] = []
        func backtrack(_ start: Int) {
            result.append(current)
            for i in start..<nums.count {
                current.append(nums[i])
                backtrack(i + 1)
                current.removeLast()
            }
        }
        backtrack(0)
        return result
    }
}

計算量: O(n × 2^n)。