항해99 2주차 - 부분집합

Today I learned
2022/01/21

회고록

1/21

항해 99, 알고리즘 1주차

교재 : 파이썬 알고리즘 인터뷰

12장 그래프

1. 이론

https://velog.io/@jsw4215/%ED%95%AD%ED%95%B499-2%EC%A3%BC%EC%B0%A8-%EA%B7%B8%EB%9E%98%ED%94%84DFSBFS-%EC%9D%B4%EB%A1%A0-%EC%A0%95%EB%A6%AC

2. 문제

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Example 2:

Input: nums = [0]
Output: [[],[0]]

Constraints:

1 <= nums.length <= 10
-10 <= nums[i] <= 10
All the numbers of nums are unique.

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

3. MySol

• Recursive DFS

def solution(inputNum):

    result = []
    prev_nodes = []
    next_nodes = []

    def dfs(nums):

        for i in range(len(nums)):
            next_nodes = nums[i:]
            next_nodes.remove(nums[i])

            prev_nodes.append(nums[i])
            result.append(prev_nodes[:])
            dfs(next_nodes)
            prev_nodes.pop()

    dfs(inputNum)

    #e를 제외한 subList와 비교하기

    result.append([])
    return result


if __name__ == '__main__':

    inputNum = [1,2,3]

    result = solution(inputNum)

    print('result : ' + str(result))

4. 배운 점

• 순열에서 DFS를 이용한 순열조합 출력을, 조금 변형하게 되면 해당 문제를 해결할 수 있다.

5. 총평

재귀, DFS 훈련