# **Leetcode筆記(Subsets)**

:::info
:information_source: 題目 : Subsets, 類型 : recursion , 等級 : medium
日期 : 2023/05/29，2023/07/10，2023/12/10，2024/10/10
:::

### 嘗試
2023/07/10
永遠有兩個選擇，要添加當前數字與不添加當前數字，選擇完後，把全部的結果放到下一層，並且進來新的數字同樣做兩種選擇
1. 需要先初始化[]
2. 每次添加一個nums列表的數字
3. 在subSet中，需要用index去跌代，因為subSet會不停增長(會memory limit exceed)
4. 需要用copy()去創造兩個獨立的變數，否則會互相連動

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        subSet = [[]]

        for n in nums:
            for i in range(len(subSet)):
                subNew = subSet[i].copy()
                subNew.append(n) # 新增
                subSet.append(subNew)
        
        return subSet

2023/12/10

class Solution(object):
    def subsets(self, nums):
        res = []
        
        def backtracking(i, path):
            if i == len(nums):
                res.append(list(path))
                return

            backtracking(i + 1, path + [nums[i]])
            backtracking(i + 1, path)
        
        backtracking(0, [])
        return res

2024/10/10

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        self.traverse(nums, res, [], 0)
        return res
    
    def traverse(self, nums, res, path, start):
        res.append(path)

        for i in range(start, len(nums)):
            self.traverse(nums, res, path + [nums[i]], i + 1)

---
### **優化**

在 Python 中，列表是可变对象，所以直接对列表进行操作可能会导致原列表的修改，所以通過使用copy，會另外複製出一串新的列表，不會對原列表產生影響

---

時間複雜度：
- 外層循環遍歷 `nums` 列表，所以它的時間複雜度為 O(len(nums))。
- 內層循環遍歷 `subset` 列表，其長度會逐步增加，但每個元素最多只會被訪問一次。所以，內層循環的總時間複雜度可以近似看作 O(2^len(nums))，因為對於每個元素，我們都需要複製一份並添加到 `subset` 中。

因此，總體時間複雜度為 O(len(nums) * 2^len(nums))。

空間複雜度：
- 初始時，我們創建了一個空列表 `subset`，佔用 O(1) 的空間。
- 隨著循環的進行，我們不斷向 `subset` 中添加新的子集，最終的 `subset` 列表的長度將達到 2^len(nums)。
- 每個子集的平均長度為 len(nums)/2，因為每個元素可能在子集中出現或不出現。
- 所以，子集的總空間佔用為 O(2^len(nums) * len(nums)/2) = O(2^len(nums) * len(nums))。

因此，總體空間複雜度為 O(2^len(nums) * len(nums))。

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        subset = [[]] # len([[]])為1

        for n in nums:
            for i in range(len(subset)):
            # 不可以用for sub in subset 
            # sub_copy = sub.copy()因為處理完一個subset
            # for 迴圈的subset就會更新，就會無限循環
            # 達到Memory Limit Exceeded
                # 先處理上一層的各個元素 + 這一層的n
                sub_copy = subset[i].copy()
                sub_copy += [n]
                # 把上一層的答案與這一層"新的"添加再一起
                subset.append(sub_copy) 
        return subset     

---

**:warning: 錯誤語法**
:::warning

:::

**:thumbsup:學習**
:::success

:::

**思路**
最一開始先初始化[[]]，然後依序遍歷nums裡面的東西，把 ( 原始subset沿用 + 原始.append新加的數字 ) ，
例如第一層就是沿用[]，再加上[1]，
第二層就是沿用[]，[1]，再加上2，即[2]，[1,2]
第三層就是沿用以上四個，再加上3

**講解連結**
https://www.youtube.com/watch?v=6mlWs0iABjs&ab_channel=%E4%BB%8A%E5%A4%A9%E6%AF%94%E6%98%A8%E5%A4%A9%E5%8E%B2%E5%AE%B3
Provided by. 今天比昨天厲害

###### tags: `recursion` `medium` `leetcode`