부분 집합(Subsets) 문제는 주어진 정수 배열의 모든 가능한 조합(멱집합, Power Set)을 찾는 알고리즘 문제입니다. 재귀적 사고를 통해 문제를 작은 단위로 분해하고, 결정 트리(Decision Tree)를 구축하여 해결하는 과정은 백트래킹의 기초를 다지는 데 매우 효과적입니다.

1. 문제 핵심 이해하기

리트코드 78번 문제는 정수로 이루어진 배열 nums가 주어졌을 때, 해당 배열로 만들 수 있는 모든 부분 집합을 반환할 것을 요구합니다. 결과에는 중복된 부분 집합이 없어야 하며, 공집합을 포함해야 합니다. 예를 들어, nums = [1, 2, 3]인 경우 결과는 다음과 같습니다. [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

2. 결정 트리를 통한 접근 방식

각 원소에 대해 우리는 두 가지 선택을 할 수 있습니다.

• 해당 원소를 부분 집합에 포함시킨다.
• 해당 원소를 부분 집합에 포함시키지 않는다.

이 과정을 트라이(Tree) 구조로 시각화하면, 배열의 각 인덱스마다 두 개의 가지가 뻗어나가는 이진 트리 형태가 됩니다. 트리의 높이는 배열의 길이와 같으며, 모든 리프 노드가 하나의 유효한 부분 집합이 됩니다.

                [ ] (시작)
              /     \
          [1] 추가    [1] 제외
           /   \        /   \
        [1,2]  [1]    [2]   [ ]

3. 구현 방법 1: 이진 선택 DFS

이 방식은 배열의 각 인덱스를 순차적으로 방문하면서, 현재 요소를 선택하는 경로와 선택하지 않는 경로를 각각 재귀적으로 탐색합니다.

class Solution {
private:
    vector result;
    vector<int> currentSubset;

public:
    vector subsets(vector<int>& nums) {
        explore(nums, 0);
        return result;
    }

    void explore(vector<int>& nums, int index) {
        // 기저 사례: 모든 원소를 검토했을 때
        if (index == nums.size()) {
            result.push_back(currentSubset);
            return;
        }

        // 1. 현재 원소를 포함하는 경우
        currentSubset.push_back(nums[index]);
        explore(nums, index + 1);

        // 2. 백트래킹: 현재 원소를 제거하고 포함하지 않는 경우 탐색
        currentSubset.pop_back();
        explore(nums, index + 1);
    }
};

이 코드는 명시적으로 '선택'과 '비선택'을 나누어 처리하므로 논리 구조가 매우 직관적입니다.

4. 구현 방법 2: 루프 기반의 조합 백트래킹

두 번째 방식은 일반적인 조합(Combination) 문제를 풀 때 자주 사용되는 템플릿입니다. 재귀 함수가 호출될 때마다 현재 상태의 path를 결과 리스트에 추가하고, 반복문을 통해 현재 인덱스 이후의 요소들을 하나씩 추가하며 깊게 탐색합니다.

class Solution {
public:
    vector subsets(vector<int>& nums) {
        vector allSubsets;
        vector<int> track;
        backtrack(nums, 0, track, allSubsets);
        return allSubsets;
    }

    void backtrack(vector<int>& nums, int start, vector<int>& track, vector& allSubsets) {
        // 매 호출마다 현재까지 구성된 track은 유효한 부분 집합임
        allSubsets.push_back(track);

        for (int i = start; i < nums.size(); i++) {
            // 원소 선택
            track.push_back(nums[i]);
            // 다음 인덱스부터 다시 탐색 시작
            backtrack(nums, i + 1, track, allSubsets);
            // 원소 제거 (상태 복구)
            track.pop_back();
        }
    }
};

이 방식의 특징은 다음과 같습니다.

• 별도의 기저 사례(Base Case) 조건문 없이 루프의 종료 조건에 의해 재귀가 자연스럽게 멈춥니다.
• i + 1을 넘겨줌으로써 이전에 선택한 원소는 다시 고려하지 않아 중복을 방지합니다.
• 코드가 간결하며 다양한 조합 및 순열 문제로 확장하기 용이합니다.

5. 두 방식의 비교

구분	이진 선택 DFS	루프 기반 백트래킹
핵심 논리	포함 여부에 따른 두 갈래 분기	현재 지점 이후의 모든 시작점 탐색
결과 추가 시점	재귀의 끝(리프 노드)에서 추가	매 재귀 호출 직후 추가
장점	상태 공간 트리가 명확함	조합론적 문제에 최적화된 구조

부분 집합 문제는 시간 복잡도가 O(2^n)에 해당합니다. 이는 각 원소가 포함되거나 포함되지 않는 두 가지 경우의 수를 갖기 때문입니다. 배열의 크기가 커질수록 연산량이 기하급수적으로 늘어나므로, 백트래킹을 사용할 때는 항상 데이터의 범위를 먼저 확인하는 것이 중요합니다.