Question: Subsets II

Solution

想法：

放與不放

但是往右邊走，如果不放數字，再繼續往下走，要放數字時，倘若放的數字與前一個一樣，那就又會走到相同的路

如圖紅色的字，如果相同，就要跳過，不然會走到相同的路。

這時候如果想成要用 Dynamic grogram 把走過的路都記起來的話，會變得相當複雜，所以就直接排除，當要放的下一個數字，與上一個相同時的情況。

檢查不放數字的那條路，要放下一個要數字時（也就是 subset 回復原狀，pop 後），是否與上一步往左邊走，放的數字相同。

因此放數字前，要先檢查。

另外上圖是經過排序後，才可以透過檢查前一個數字，來查看現在的數字是否重複，所以拿到 list 之前要先 sort，python sort 的時間複雜度是 O(nlogn)

但 DFS 的時間複雜度是 n * 2^n，所以沒差～

Time Complexity: O(n * 2 ^ n)

class Solution:

    def subsetsWithDup(self, nums: list[int]) -> list[list[int]]:

        res = list()

        nums.sort()

        subset = list()

        def dfs(i):

            print(i)

            if i > len(nums) - 1:

                res.append((subset.copy()))

                return

            # All subsets that include nums[i]

            subset.append(nums[i])

            dfs(i + 1)

            subset.pop()

            # All subsets that exclude nums[i]

            while i + 1 < len(nums) and nums[i] == nums[i + 1]:

                i += 1 

            dfs(i + 1)

        dfs(0)

        return res