숫자로 이루어진 집합이 하나 주어졌다고 가정해 봅시다. 우리가 해야 할 일은 이 집합에서 만들 수 있는 모든 부분집합을 생성하는 것입니다. 이렇게 만들어진 전체 집합을 멱집합(Power Set)이라고 부릅니다.
예를 들어 집합이 [1, 2, 3]이라면, 멱집합은 다음과 같습니다.
[[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]
그럼 문제를 단계별로 풀어보겠습니다.
문제 해결 접근 방식
이 문제는 재귀(Recursion) 기법으로 해결할 수 있습니다. 재귀 함수의 이름을 solve()라고 하고, 이 함수는 숫자 배열(nums), 임시 배열(temp), 결과 리스트(res), 그리고 현재 인덱스(index)를 매개변수로 받는다고 정의하겠습니다.
solve() 함수의 동작 과정
- index가 nums의 길이와 같아지면, temp의 복사본을 만들어 res에 추가한 후 함수를 종료합니다.
- temp[index]를 0으로 설정한 뒤, solve(nums, temp, res, index + 1)을 호출합니다. (해당 원소를 포함하지 않는 경우)
- temp[index]를 1로 설정한 뒤, solve(nums, temp, res, index + 1)을 다시 호출합니다. (해당 원소를 포함하는 경우)
즉, 각 인덱스 위치의 원소에 대해 "포함한다 / 포함하지 않는다" 두 가지 선택지를 모두 탐색하는 방식입니다. n개의 원소가 있으면 총 2ⁿ개의 부분집합이 만들어집니다.
메인 함수의 동작 과정
- res를 빈 리스트로 초기화합니다.
- nums와 같은 크기의 temp 리스트를 만들고 0으로 채웁니다.
- solve(nums, temp, res, 0)을 호출해 모든 조합을 생성합니다.
- main_res를 빈 리스트로 초기화합니다.
- res에 담긴 각 리스트를 순회하면서, 값이 1인 위치의 nums[i]만 골라 새로운 temp 리스트에 추가합니다.
- 완성된 temp를 main_res에 삽입합니다.
- 모든 순회가 끝나면 main_res를 반환합니다.
이제 실제 구현 코드를 통해 더 자세히 이해해 보겠습니다.
구현 예제 코드
class Solution(object):
def subsets(self, nums):
temp_result = []
self.subsets_util(nums,[0 for i in range(len(nums))],temp_result,0)
main_result = []
for lists in temp_result:
temp = []
for i in range(len(lists)):
if lists[i] == 1:
temp.append(nums[i])
main_result.append(temp)
return main_result
def subsets_util(self,nums,temp,result,index):
if index == len(nums):
result.append([i for i in temp])
return
temp[index] = 0
self.subsets_util(nums,temp,result,index+1)
temp[index] = 1
self.subsets_util(nums, temp, result,index + 1)
ob1 = Solution()
print(ob1.subsets([1,2,3,4]))입력
[1,2,3,4]
출력
[[], [4], [3], [3, 4], [2], [2, 4], [2, 3], [2, 3, 4], [1], [1, 4], [1, 3], [1, 3, 4], [1, 2], [1, 2, 4], [1, 2, 3], [1, 2, 3, 4]]
정리
위 코드는 각 원소를 부분집합에 포함할지 여부를 0과 1로 표현하는 비트마스킹 개념과 재귀를 결합한 방식입니다. 시간 복잡도는 부분집합의 개수가 2ⁿ개이므로 O(n × 2ⁿ)이 됩니다. 입력 크기가 작은 경우에는 충분히 효율적이며, 코딩 테스트에서 자주 등장하는 대표적인 백트래킹 유형 문제이므로 반드시 익혀두면 좋습니다.