47. Permutations II

Medium

Description

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

Example:

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

Intuition#

核心思路：排序後回溯，用「同層跳過重複」技巧避免產生重複排列。

與 46. Permutations 相比，多了重複元素
先排序，使重複元素相鄰
同一層遞迴中，相同值只用第一個（跳過後續相同的）
用 used 陣列追蹤哪些元素已被選取

Approaches#

1: 用 HashSet 去重#

概念: 與基本排列相同，但用 HashSet 存結果去重
時間複雜度: O(n! * n) - 最差情況
空間複雜度: O(n! * n)

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

        fun backtrack() {
            if (current.size == nums.size) {
                resultSet.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
            }
        }

        nums.sort()
        backtrack()
        return resultSet.toList()
    }
}

⭐2: 排序 + 回溯剪枝#

概念: 排序後，同一層中遇到與前一個相同且前一個未被使用的元素，跳過以避免重複
時間複雜度: O(n! * n) - 但實際因剪枝遠少於此
空間複雜度: O(n)

class Solution {
    fun permuteUnique(nums: IntArray): List<List<Int>> {
        nums.sort()
        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
                // 同層剪枝：相同值且前一個未使用，跳過
                if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue

                used[i] = true
                current.add(nums[i])
                backtrack()
                current.removeAt(current.lastIndex)
                used[i] = false
            }
        }

        backtrack()
        return result
    }
}

🔑 Takeaways#

Pattern: 含重複元素的排列 → 排序 + 同層跳過重複
關鍵技巧: 剪枝條件 nums[i] == nums[i-1] && !used[i-1] 表示同層已用過相同值；這與 40. Combination Sum II 和 90. Subsets II 的去重邏輯一致