Leetcode 78. Subsets (DFS backtracking)

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

Subsets - LeetCode

 

---

이 문제는 DFS의 Back tracking 을 활용한 문제인데요 저는 아래와 같이 풀이를 했습니다

 

	from itertools import combinations
	class Solution:
   	def subsets(self, nums: List[int]) -> List[List[int]]:        
        
        #방법 1 tertools.combinations를 활용한 조합생성
        # res = []
        # for i in range(1,len(nums)+1):
        #     res.extend(itertools.combinations(nums,i))
        # res.append([])
        # return res
        
         #방법 2 dfs와 재귀문을 활용한 풀이
#         res = [[]]
#         def btrack(c,cur,i):
#             if len(cur) == c:
#                 res.append(list(cur))
#                 return
#             if i >= len(nums):
#                 return
#             for i in range(len(nums)):
#             	cur.append(nums[i])
#            	btrack(c,cur,i+1)
#             	cur.pop()
#             	btrack(c,cur,i+1)
                
            
#         for i in range(1,len(nums)+1):
#             btrack(i,[],0)
#         return res

 

 

dfs 재귀문과 더불어, 다른 분들의 풀이에서 공통적으로 사용한 개념이 바로 아래 그림에서 잘 나타나 있습니다.

 

Source: Leetcode discussion, gtshepard

 

 

---

DFS 재귀문을 활용한 다른 풀이)

def subsets(self, nums: List[int]) -> List[List[int]]:
	res, path = [], []
        self.dfs(0, res, path, nums)
        return res
		
 def dfs(self, index, res, path, nums):
        res.append(list(path)) 
        for i in range(index, len(nums)):
            path.append(nums[i])
            self.dfs(i+1, res, path, nums)
            path.pop()

 

FOR 문을 활용한 간단한 풀이 )

def subsets(self, nums: List[int]) -> List[List[int]]:

	result = [[]]

	for n in nums:
    		for i in range(len(result)):
        		result.append(result[i]+[n])
	return result

 

이 풀이는 어떻게 이렇게 간단하게 풀어냈지 싶을 정도로 신기했던 풀이인데요 

문제의 패턴을 파악해서 풀이로 잘 풀어낸 것 같습니다 ㅜ