LeetCode 문제풀이 (Subsets)

오랜만에 주말에 집에 있게 되어 심심하던차,, 백만년만에 LeetCode 문제를 풀어보았습니다. https://www.youtube.com/watch?v=cUT3S4N8fS8 유튜브를 보다 알고리즘에 관련 영상이 떠서 보고 있었는데요, 해당 영상에서 소개해주신 문제를 보다 내가 풀수 있을까? 라는 의문이 들어 급 문제를 풀게 되었습니다. 제가 해당 문제를 풀었을 때 이용한 아이디어는 다음과 같습니다. "배열에 있는 모든 정수들은 subset 에 포함되거나 포함되지 않는 2가지 경우의 수가 있으니 각 경우의 수로 재귀함수를 돌면 되겠다." Backtracking 이라는 알고리즘을 떠올린 건 아니고 그냥 떠오르는 아이디어를 가지고 코드 구현을 하니 다행히 바로 통과가 되네요 ㅎㅎ,, * Name: Subsets * Difficulty: Medium * Algorithm: Backtracking * Time Complexity: O(2^n * n) * Space Complexity: O(2^n * n) * 문제 링크: https://leetcode.com/problems/subsets/description/ class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: answer = [] self.back_tracking(answer, [], nums, 0) return answer def back_tracking(self, answer, tmp, nums, depth): if depth == len(nums): answer.append(tmp) return self.back_tracking(answer, tmp + [nums[depth]], nums, depth + 1) self.back_tracking(answer, tmp, nums, depth + 1)