LeetCode 78(Subsets, Python)

1. 문제 링크

• https://leetcode.com/problems/subsets/

Subsets - LeetCode

2. 문제 설명

• unique elements로 구성된 array nums가 주어졌을 때, 모든 가능한 subsets를 반환
  • 중복 subsets는 허용하지 않으며, 어떤 순서로든 반환 가능
• 예시1) nums = [1,2,3], output = [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]
• 예시2) nums = [0], output = [[], [0]]

3. 처음 풀이 

• 최근 backtracker 문제를 연속으로 두번 풀어서 이번에도 문제를 보고 backtracker로 접근하였음
• backtrack함수는 path, start, num 세가지 인자를 받고
  • 만약 path의 길이가 num과 동일하면 output에 해당 path를 append 시키고, 
  • nums 에 대해 start 부터 for문을 돌면서, path에 nums[i]가 포함되있지 않으면,
    • path에 append한 후, start를 i+1로 변경하여 backtracker를 호출 후 원래 상태로 원복 (path.pop())
  • 그리고 num가 1보다 큰 경우에는 num을 하나 줄인 backtrack함수를 호출
• 여기서 문제는 backtrack을 두번 호출한다는 것 . runtime이 70%도 나오긴 했지만, 대부분이 하위 10%에서 머물렀음

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:

        def backtrack(path, start, num):
            if len(path) == num:
                output.append(path.copy())
                return

            else:
                for i in range(start, len(nums)):
                    if nums[i] not in path:
                        path.append(nums[i])
                        backtrack(path,i+1,num)
                        path.pop()
                    if num > 1:
                        backtrack(path,i+1,num-1)

        output = [[]]
        backtrack([],0,len(nums))

        return output

 

4. 다른 풀이 

• 처음에 나는 다양한 길이의 list를 append해야 하므로, len(nums)를 인자로 받고, 이를 1이 될 때까지 줄여나갔는데 
• 굳이 그렇게 할 필요가 없었다!! 
• 생각해보면, 그냥 return하는 조건을 걸지 않고, 
  • for문을 돌리면서 그 값을 그냥 output에 append 시켜도,
  • len(nums)이하 길이의 list만 output에 append 되기 때문에
  • 위에서 한 것처럼 복잡한 조건을 추가할 필요가 없었다. 

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:

        def backtrack(start, path):
            output.append(path[:])

            for i in range(start, len(nums)):
                path.append(nums[i])
                backtrack(i + 1, path)
                path.pop()

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

 

• 제로_콜라의 풀이 
  • backtracker로 재귀를 쓰지 않고, 깔끔하게 풀었다. 
  • nums가 [1,2,3]이면 
    • 처음에는 result가 [[], [1]] 이 되고, 
    • 그 다음 iteration에서는 [[],[1],[2],[1,2]]가 되고
    • 마지막 iteration에서는 [[],[1],[2],[1,2],[1,3],[2,3],[1,2,3]]이 되는 구조로 간단히 for문으로 해결

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = [[]]
        for num in nums:
            for subset in result[:]:
                result.append(subset + [num])
        
        return result

 

5. 배운 점 

• backtracker 익숙해지기! + 다른 algorithm, 로직으로도 해결 가능.