[Leetcode 78] - Subsets w/ Python

 

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.

 

 

 

숫자 배열이 주어졌을때 가능한 모든 하위 집합을 리턴

중복된 집합을 배제해야된다

 

 

 

https://leetcode.com/problems/subsets/description/

 

 

---

 

 

 

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]]

 

 

 

---

 

 

 

백트래킹으로 문제를 풀이했다

길이가 3인 배열이 주어진다면 길이가 0, 1, 2, 3을 고려해야되서 for loop으로 각각 확인하는 방법을 택했다

 

 

1. 스택의 길이가 현재 고려하는 숫자라면 ans에 추가

2. 계속해서 현재 num을 stack에 추가

3. 다음 숫자를 보기 위해 index를 +1 하고 backtrack 재귀

 

 

class Solution:
    def subsets(self, nums):
        ans = []
        stack = []
        k = len(nums)
        
        def backtrack(start, length):
            if len(stack) == length:
                ans.append([*stack])
                return
            
            for i in range(start, k):
                stack.append(nums[i])
                backtrack(i + 1, length)
                stack.pop()
            return
        
        
        for i in range(k + 1):
            backtrack(0, i)
            
        return ans

 

 

 

---

 

 

Neetcode에서 사용된 풀이가 휠씬 깔끔해서 꼭 적고 싶었다

런타임은 내가 작성한 코드가 조금 빠르다는걸 확인할 수 있었다

 

class Solution:
    def subsets(self, nums):
        ans = []
        stack = []
        
        def dfs(i):
            if i >= len(nums):
                ans.append(stack.copy())
                return
            
            stack.append(nums[i])
            dfs(i + 1)

            stack.pop()
            dfs(i + 1)
        
        dfs(0)
        return ans