50. Permutations

読了目安約1分

Greedy / Backtracking / LeetCode 46 (Medium) — 相異なる整数のすべての順列をバックトラッキングで列挙する。

この章の目次

問題

LeetCode 46. Permutations（Medium / カテゴリ: Greedy / Backtracking）

相異なる整数の配列 nums のすべての順列を列挙して返します。返す順序は自由です。長さは最大 6 なので、n! 通りをすべて作って間に合います。

考え方

ヒント 1

「ここまでに選んだ列」を 1 要素ずつ伸ばしていきます。長さが n に達したら、順列が 1 つ完成です。

ヒント 2

使用済みかどうかのフラグ配列 used を持ち、未使用の要素を順に試します。 1 つ試して再帰から戻ったら、選択を取り消して次の候補へ進みます。この「試して、戻して、次を試す」がバックトラッキングです。

Swift 実装のポイント

ネストした関数で再帰を書くと、result や used を引数で引き回さずに済みます。
current.append(nums[i]) して再帰したら、戻った直後に current.removeLast() と used[i] = false で必ず元に戻します。
出力の順序は実装依存です。テストコードは結果と期待値の両方をソートしてから比較しています。

模範解答

Swift
class Solution {
    func permute(_ nums: [Int]) -> [[Int]] {
        var result: [[Int]] = []
        var current: [Int] = []
        var used = [Bool](repeating: false, count: nums.count)
        func backtrack() {
            if current.count == nums.count {
                result.append(current)
                return
            }
            for i in 0..<nums.count where !used[i] {
                used[i] = true
                current.append(nums[i])
                backtrack()
                current.removeLast()
                used[i] = false
            }
        }
        backtrack()
        return result
    }
}

計算量: O(n × n!)。