코딩테스트 문제 (13) - 부분 집합

문제

입력으로 주어진 배열에 대해 부분 집합을 return하는 문제입니다.

1. array = [1,2,3]
=> [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

풀이

먼저 결과 형식은 리스트 안에 부분집합을 추가하는 형태입니다. 배열을 for 루프로 순회하면서 공집합부터 ([]) 추가하고 첫 번째 원소 1에 대해서 [1], [1,2], [1,2,3], [1,3] 을 추가하고 그 다음 원소 2에 대해 [2],[2,3] 을 추가하는 식을 생각해볼 수 있겠네요. 바로 그래프의 깊이우선탐색 (dfs) 를 이용하면 풀이가 가능합니다. 

kaggle.com의 notebook으로 작성한 풀이는 다음과 같습니다.

 

홍머스 정리

• 난이도: 중, 그래프 구조를 생각해야 한다.

참조

• <파이썬 알고리즘 인터뷰>, p355-356
• leetcode.com/problems/subsets/