Subsets Algorithm

from typing import List

class Solution:
    """
    LeetCode Subsets 問題の解決クラス
    バックトラッキングによる部分集合生成
    """

    def subsets(self, nums: List[int]) -> List[List[int]]:
        """
        与えられた整数配列の全ての部分集合を生成する

        Args:
            nums (List[int]): ユニークな整数配列 (1 <= len(nums) <= 10)

        Returns:
            List[List[int]]: 全ての部分集合を格納したリスト

        Time Complexity: O(2^n * n)
        Space Complexity: O(n) - 再帰スタック + 一時リスト
        """
        result: List[List[int]] = []
        path: List[int] = []

        def backtrack(start: int) -> None:
            """
            バックトラッキング用の内部関数

            Args:
                start (int): 探索開始位置
            """
            # 現在の部分集合を結果に追加（シャローコピー必須）
            result.append(path[:])

            # 残りの要素を順番に探索
            for i in range(start, len(nums)):
                # 要素を選択
                path.append(nums[i])

                # 再帰的に探索を続行
                backtrack(i + 1)

                # バックトラッキング: 選択を取り消し
                path.pop()

        # 最初の位置から探索開始
        backtrack(0)
        return result

# 使用例
if __name__ == "__main__":
    solution = Solution()

    # Test Case 1
    nums1 = [1, 2, 3]
    result1 = solution.subsets(nums1)
    print(f"Input: {nums1}")
    print(f"Output: {result1}")
    print()

    # Test Case 2
    nums2 = [0]
    result2 = solution.subsets(nums2)
    print(f"Input: {nums2}")
    print(f"Output: {result2}")