Open seungriyou opened 8 months ago
https://leetcode.com/problems/subsets/
헷갈릴 때는 트리 형태로 재귀 구조를 그려보면 쉽다!
backtracking을 사용하여 모든 호출마다 현 시점의 subset 리스트를 기록한다.
subset
iterative 한 방법으로도 가능하다.
nums
지금까지 모아온 subset 들에 대해 각각에 현재 보고 있는 num을 추가한 리스트를 append 해준다.
num
append
간결하게 코드를 작성하려면 list comprehension을 사용하면 된다.
O(n * 2^n)
2^n
n
Approach
Idea 1: Recursive (Backtracking)
backtracking을 사용하여 모든 호출마다 현 시점의
subset리스트를 기록한다.Idea 2: Iterative 💡
iterative 한 방법으로도 가능하다.
nums를 순회한다.지금까지 모아온 subset 들에 대해 각각에 현재 보고 있는
num을 추가한 리스트를append해준다.Complexity
O(n * 2^n)(2^n: subset의 개수,n: list 복사)O(n * 2^n)