90. Subsets II

Medium

Description

給定一個整數陣列 nums（可能包含重複元素），回傳所有可能的子集。結果不能包含重複的子集，可以任意順序回傳。

Example:

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

Intuition#

核心思路：在 Subsets I 的基礎上，先排序再跳過同層的重複元素，即可去重。

有重複元素 → 排序讓相同元素相鄰
同一層遞迴中，如果 nums[i] == nums[i-1] 且 i > start，代表同層已經用過這個值，跳過
關鍵區分：「同層跳過」vs「不同層可以選」——排序 + i > start 的判斷精確做到這一點

Approaches#

1: Backtracking + HashSet 去重#

概念: 用 HashSet 儲存子集（排序後的 List），自動去重
時間複雜度: O(n * 2^n)
空間複雜度: O(n * 2^n) - HashSet 儲存

class Solution {
    fun subsetsWithDup(nums: IntArray): List<List<Int>> {
        nums.sort()
        val result = HashSet<List<Int>>()
        val current = mutableListOf<Int>()

        fun backtrack(start: Int) {
            result.add(ArrayList(current))
            for (i in start until nums.size) {
                current.add(nums[i])
                backtrack(i + 1)
                current.removeAt(current.lastIndex)
            }
        }

        backtrack(0)
        return result.toList()
    }
}

⭐2: Backtracking + 同層跳過#

概念: 排序後，在同一層遞迴中，跳過與前一個相同的元素（i > start && nums[i] == nums[i-1]）
時間複雜度: O(n * 2^n)
空間複雜度: O(n) - 遞迴深度

class Solution {
    fun subsetsWithDup(nums: IntArray): List<List<Int>> {
        nums.sort()
        val result = mutableListOf<List<Int>>()
        val current = mutableListOf<Int>()

        fun backtrack(start: Int) {
            result.add(ArrayList(current))

            for (i in start until nums.size) {
                if (i > start && nums[i] == nums[i - 1]) continue  // 同層跳過重複
                current.add(nums[i])
                backtrack(i + 1)
                current.removeAt(current.lastIndex)
            }
        }

        backtrack(0)
        return result
    }
}

🔑 Takeaways#

Pattern: 有重複元素的回溯 = 排序 + 同層跳過，這個技巧適用於子集、組合、排列的去重版本
關鍵技巧: i > start && nums[i] == nums[i-1] 是回溯去重的萬能公式；理解「同層」vs「不同層」的區別是關鍵