46. Permutations

Medium

Description

給定一個不含重複數字的整數陣列 nums，回傳其所有可能的排列。可以任意順序回傳答案。

Example:

Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Intuition#

核心思路：排列和子集/組合的差異在於「順序有關」，因此每層都從頭開始選，但不能選已選過的元素。

排列的搜尋樹：第一層選第一個位置的數，第二層選第二個位置的數 …
每個位置可以放任何「還沒被使用」的數 → 需要一個 used 陣列或集合追蹤
當 current 長度等於 nums 長度，就得到一個完整排列

Approaches#

1: Backtracking + Used 陣列#

概念: 用 boolean 陣列記錄哪些數已被使用，每層遍歷所有數，跳過已用的
時間複雜度: O(n * n!) - n! 個排列，每個長度 n
空間複雜度: O(n) - 遞迴深度 + used 陣列

class Solution {
    fun permute(nums: IntArray): List<List<Int>> {
        val result = mutableListOf<List<Int>>()
        val current = mutableListOf<Int>()
        val used = BooleanArray(nums.size)

        fun backtrack() {
            if (current.size == nums.size) {
                result.add(ArrayList(current))
                return
            }

            for (i in nums.indices) {
                if (used[i]) continue
                used[i] = true
                current.add(nums[i])
                backtrack()
                current.removeAt(current.lastIndex)
                used[i] = false
            }
        }

        backtrack()
        return result
    }
}

⭐2: Backtracking + Swap#

概念: 用 swap 代替 used 陣列。將 index 左邊視為「已選」，右邊視為「可選」，每次從右邊挑一個 swap 到當前位置
時間複雜度: O(n * n!)
空間複雜度: O(n) - 遞迴深度（不需要額外 used 陣列）

class Solution {
    fun permute(nums: IntArray): List<List<Int>> {
        val result = mutableListOf<List<Int>>()

        fun backtrack(start: Int) {
            if (start == nums.size) {
                result.add(nums.toList())
                return
            }

            for (i in start until nums.size) {
                nums[start] = nums[i].also { nums[i] = nums[start] }
                backtrack(start + 1)
                nums[start] = nums[i].also { nums[i] = nums[start] }
            }
        }

        backtrack(0)
        return result
    }
}

🔑 Takeaways#

Pattern: 排列問題的核心差異 — 每層從頭遍歷（不是從 start 開始），用 used 陣列或 swap 避免重複選取
關鍵技巧: Swap 法省去 used 陣列，原地操作；子集用 start index，排列用 used/swap，兩者模板要能區分