항해99 2주차 - 부분집합
Today I learned
2022/01/21
회고록
1/21
항해 99, 알고리즘 1주차
교재 : 파이썬 알고리즘 인터뷰
12장 그래프
1. 이론
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 훈련
Author And Source
이 문제에 관하여(항해99 2주차 - 부분집합), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jsw4215/항해99-2주차-부분집합저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)