Python Algorithm Q37

Q37 Subsets

---

Q

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.

Sample Input

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.

1. My Own Solution

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

        def dfs(index: int, currentlist: List):
            ans.append(currentlist)

            for i in range(index, len(nums)):
                dfs(i+1, currentlist + [nums[i]])

        dfs(0, [])
        return ans

# test set
a = Solution()
b = [2, 3, 5]
a.subsets(b)

Q36으로 더 단단해진 DFS 문제풀이 실력이 빛을 발한 것 같다 ㅎㅎ 얘도 1트클. subset이라는 거꾸로 내려가는 개념이 조금 생소하긴 했는데 얘도 큰 틀에서는 비슷했던 것 같다. 첫 번째 원소를 포함하는 모든 subset들을 싹다 append하고, 이제 첫 번째 원소를 아예 배재한 상태에서 다음 원소로 넘어가서 다시 재귀를 시작하도록 했다. 결과도 훌륭하고 연산 시간도 굉장히 훌륭한 풀이가 나왔다.

2. Given Solution

내 풀이랑 완전히 똑같더라 ㅎㅎ 그래서 생략

Overall Review

DFS 그래프로 표현이 되는 애들은 이제 자연스럽게 재귀를 통해 끝까지 탐색하도록 코드를 짤 수 있을 것 같다. 처음에 DFS에 대해 배울때는 재귀보단 stack을 더 많이 쓰지 않을까 싶었는데 대부분의 풀이가 재귀로 구현되어 있고 실제로 풀이를 보니가 재귀가 더 깔끔하고 이쁘게 코드를 짤 수 있는 것 같다. 재귀함수 무한 루프 때문에 PTSD가 있어서 가급적 안쓰고 있었는데 이 챕터에서 여태 코딩 배우면서 써본 재귀보다 훨씬 더 많이 써본 것 같다 ㅋㅋ