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)