📋 アルゴリズム概要

🔄 ステップバイステップ解説

💻 Python実装（LeetCode形式）

from typing import List
class Solution:
"""
LeetCode 90: Subsets II
重複要素を含む配列からユニークな全部分集合を生成
反復的拡張法 + prev_size による重複制御
Time: O(n·2^n), Space: O(1) extra (excluding output)
"""

def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
    """
    重複要素を含む配列からユニークな全部分集合を返す

    Args:
        nums: 整数配列（重複を含む可能性あり）

    Returns:
        重複のないすべての部分集合のリスト

    Examples:
        >>> Solution().subsetsWithDup([1,2,2])
        [[], [1], [1,2], [1,2,2], [2], [2,2]]

        >>> Solution().subsetsWithDup([0])
        [[], [0]]
    """
    # ステップ1: ソートして同値を隣接させる
    # これにより重複判定が O(1) で可能になる
    arr: List[int] = sorted(nums)

    # ステップ2: 空集合で初期化
    res: List[List[int]] = [[]]

    # prev_size: 直前イテレーション開始時の res の長さ
    # 重複要素の拡張範囲を制御するために使用
    prev_size: int = 0

    # ステップ3: 各要素について部分集合を拡張
    for i, v in enumerate(arr):
        # 現在の部分集合数を保存
        size: int = len(res)

        # ステップ4: 拡張開始位置を決定
        # 重複要素なら前回追加分のみ拡張、そうでなければ全体を拡張
        if i > 0 and v == arr[i - 1]:
            # 重複: 前回イテレーションで追加された部分のみ拡張
            start: int = prev_size
        else:
            # 新規要素: すべての既存部分集合を拡張
            start = 0

        # ステップ5: 部分集合を拡張
        # start から size-1 までの各部分集合に v を追加
        for j in range(start, size):
            base = res[j]
            # Python の list 連結は C 実装で高速
            res.append(base + [v])

        # ステップ6: 次回イテレーション用に現在のサイズを保存
        prev_size = size

    return res

📊 視覚的図解・フローチャート

              flowchart TD
    Start([開始: subsetsWithDup]) --> Sort["配列をソート
arr = sorted(nums)"]
    Sort --> Init["結果を初期化
res = [[]]
prev_size = 0"]
    Init --> LoopCheck{"配列の全要素を
処理したか?"}

    LoopCheck -->|No| GetElement["現在の要素 v を取得
i番目の要素"]
    LoopCheck -->|Yes| Return([結果を返す: res])

    GetElement --> SaveSize["現在のサイズを保存
size = len(res)"]
    SaveSize --> DupCheck{"重複要素か?
i > 0 かつ
v == arr[i-1]"}

    DupCheck -->|Yes| SetStartPrev["拡張開始位置を設定
start = prev_size
前回追加分のみ拡張"]
    DupCheck -->|No| SetStartZero["拡張開始位置を設定
start = 0
全体を拡張"]

    SetStartPrev --> InnerLoop["内側ループ開始
j = start to size-1"]
    SetStartZero --> InnerLoop

    InnerLoop --> InnerCheck{"j < size?"}

    InnerCheck -->|Yes| CreateSubset["新しい部分集合を作成
base = res[j]
new = base + [v]"]
    InnerCheck -->|No| UpdatePrev["prev_sizeを更新
prev_size = size"]

    CreateSubset --> AppendRes["結果に追加
res.append(new)"]
    AppendRes --> IncrJ["j++"]
    IncrJ --> InnerCheck

    UpdatePrev --> IncrI["i++"]
    IncrI --> LoopCheck

    style Start fill:#e1f5e1
    style Return fill:#e1f5e1
    style DupCheck fill:#fff4e1
    style LoopCheck fill:#fff4e1
    style InnerCheck fill:#fff4e1
    style CreateSubset fill:#e1e5f5
    style AppendRes fill:#e1e5f5
    style Sort fill:#f5e1e1
            

⚡ 計算量説明

🔍 エッジケースと検証観点