03/11 코딩테스트 문제풀이 - 78. Subsets (Leetcode) ⭐⭐⭐⭐⭐

문제

• Leetcode 알고리즘 문제
• 78. Subsets (Medium)
• 문제 내용 : [링크]
  

내가 작성한 코드

class Solution:
    def subsets(self, nums):
        def backtrack(s, path):
            n = len(nums)
            result.append(path)

            if len(path) == n:
                return

            for i in range(s, n):
                if nums[i] not in path:
                    path.append(nums[i])
                    backtrack(i+1, path[:])
                    path.pop()

        result = []
        backtrack(0, [])
        return result

• 주어진 nums로 만들 수 있는 부분집합을 모두 구하는 문제이다.

• backtracking을 통한 완전탐색을 통해 문제를 접근

• backtrack 함수 실행시, 먼저 path(부분집합)을 result에 append 해 준다.

• 이후 path의 길이가 len(nums)와 같은 경우, return 해 준다.

• 위에서 path의 길이가 len(nums)와 같지 않다면, for문을 통해 s부터 n까지의 숫자 중 인덱스 하나를 선택해준다. 이후 nums[i]가 path에 없다면 append 해 준다.

• 이후 다시 backtrack(i+1, path[:])를 통해 백트레킹 해준다.

• 첫 nums[i]를 통해 모든 부분집합이 result에 구해졌으면, path.pop()해주고 다음 nums[i]에 대한 부분집합을 구해준다.

• 첫 backtrack 실행을 해 준다. (backtrack(0, []))

• result를 출력해준다.

⭐⭐⭐⭐⭐

• 완전탐색의 기초가 되는 아주 중요한 문제! 계속 반복해서 풀어보기.