給定一個不含重複數字的整數陣列
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
TIP
核心思路：排列和子集/組合的差異在於「順序有關」，因此每層都從頭開始選，但不能選已選過的元素。
- 排列的搜尋樹：第一層選第一個位置的數，第二層選第二個位置的數 …
- 每個位置可以放任何「還沒被使用」的數 → 需要一個 used 陣列或集合追蹤
- 當 current 長度等於 nums 長度，就得到一個完整排列
Approaches
1. Backtracking + Used Array — O(n * n!) / O(n)
- Idea: 用 boolean 陣列記錄哪些數已被使用，每層遍歷所有數，跳過已用的
- Time:
O(n * n!)- n! 個排列，每個長度 n - Space:
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 — O(n * n!) / O(n)
- Idea: 用 swap 代替 used 陣列。將 index 左邊視為「已選」，右邊視為「可選」，每次從右邊挑一個 swap 到當前位置
- Time:
O(n * n!) - Space:
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 避免重複選取
- Key trick: Swap 法省去 used 陣列，原地操作；子集用 start index，排列用 used/swap，兩者模板要能區分