資訊

• Question: 78. Subsets
• From: Leetcode Daily Challenge 2024.05.21
• Difficulty: Medium

---

目錄

• 資訊
• 目錄
• 題目
• 解法
  • 概念
  • 程式碼
• 複雜度
  • 時間複雜度
  • 空間複雜度

---

題目

Given an integer array nums of unique elements, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

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

Example 2:

• Input: nums = [0]
• Output: [[],[0]]

Constraints:

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• All the numbers of nums are unique.

---

解法

概念

久違沒刷 leetcode 了，因為晚上要考 CPE 多少碰一下

這次是之前看過的題目，就是給一個 array，找出他所有的 subset，不難，就是明顯的 backtracking 題目，但怎麼做比較麻煩

不用 bit manipulation 是因為懶的用了，覺得多加一些 bit 上去不會比較方便

概念是這樣的，一開始不管是誰都會有一個 subset 是空集合，所以預設答案是 [[]] 這樣，之後每一輪都會走訪一個元素，然會會把元素一一 append 到原本的 ans 中，當然原本的 ans 不能動到，因為那也是一個答案，所以會用 copy 的方式實作

原理就像把二進位數字寫出來看，假設有三個 bit，要描述所有情況就會像這樣列出來：

000
001
010
011
100
101
110
111

000 就是空集合，而可以看到，假設現在走訪最高 bit，其實就是把之前的情況複製下來，然後加上一輪有他的版本，跟這題的概念一模一樣，透過這個方法就可以很好的做到 backtracking 所有 subset

程式碼

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = [ [] ]
        for i in range(len(nums)):
            tmp = copy.deepcopy(ans)
            for j in range(len(tmp)):
                tmp[j].append(nums[i])
            for j in range(len(tmp)):
                ans.append(tmp[j])
        return ans

---

複雜度

時間複雜度

基本上是列舉所有情況了，所以會是

$O(2^n)$

空間複雜度

空間也差不多，就是要儲存解答的空間，所以也是

$O(2^n)$