[Python] LeetCode 78. Subsets

leetcode.com/problems/subsets/

Subsets - LeetCode

부분집합을 만들어야 하는 문제에서,

permutation / combination 라이브러리는 모든 경우의 수를 iterate 형태로 반환하기 때문에 시간초과가 발생할 수 있었다.

 

부분집합을 dfs 방식으로 생성하는 기본 문제이자 코드.

아래 코드는 이 책을 참고해서 작성하였다.

파이썬 알고리즘 인터뷰 국내도서 저자 : 박상길 출판 : 책만 2020.07.15 상세보기

 

 

	class Solution:
	def subsets(self, nums: List[int]) -> List[List[int]]:
	# 트리 구조의 dfs로 해결하기
	result = []
	def dfs(idx, path):
	result.append(path)
	# idx 순서대로 경로를 만들면서 dfs 연산
	for next_idx in range(idx, len(nums)):
	dfs(next_idx + 1, path + [nums[next_idx]])
	dfs(0, [])
	return result

view raw [Leetcode] Subsets.py hosted with ❤ by GitHub