문제 링크

78. 부분집합 - LeetCode

아래 문제 설명과 예시는 LeetCode에서 가져왔습니다.

문제 설명

정수 배열 nums가 주어집니다. 배열의 원소는 서로 다릅니다. 이 배열의 가능한 모든 부분집합(멱집합)을 반환하세요.

해답 집합은 중복된 부분집합을 포함하면 안 됩니다. 해답은 임의의 순서로 반환할 수 있습니다.

예시 1:

<strong>입력:</strong> nums = [1,2,3]
<strong>출력:</strong> [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

예시 2:

<strong>입력:</strong> nums = [0]
<strong>출력:</strong> [[],[0]]

제약 조건:

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums의 모든 원소는 서로 다릅니다.

일반적인 백트래킹 템플릿

백트래킹은 선택, 재귀, 선택 취소의 과정을 반복하여 모든 가능한 상태를 탐색합니다. 조합, 순열, 부분집합 문제에 공통으로 적용할 수 있는 형태는 다음과 같습니다.

void backtrack(상태, 깊이) {
    if (탐색을_끝낼_조건) {
        결과에_기록(상태);
        return;
    }

    for (각 후보 choice : 현재_깊이의_후보들) {
        if (!유효한_선택(choice)) continue;

        선택_적용(상태, choice);
        backtrack(상태, 깊이 + 1);
        선택_취소(상태, choice);
    }
}

부분집합 문제에서는 각 원소를 "포함한다" 또는 "포함하지 않는다"로 결정하는 이진 선택 트리로 볼 수 있습니다.

void subsetDfs(int[] values, int idx, List<Integer> path, List<List<Integer>> result) {
    if (idx == values.length) {
        result.add(new ArrayList<>(path));
        return;
    }

    // 현재 원소를 포함하지 않는 경우
    subsetDfs(values, idx + 1, path, result);

    // 현재 원소를 포함하는 경우
    path.add(values[idx]);
    subsetDfs(values, idx + 1, path, result);
    path.remove(path.size() - 1);
}

핵심 요소는 다음과 같습니다.

• 선택과 취소: 원소를 path에 넣었다가 재귀가 끝나면 다시 제거합니다.
• 기저 조건: 모든 원소를 검사한 시점에 현재 path를 결과에 추가합니다.
• 가지치기: 필요하면 유효하지 않은 선택을 건너뛰어 탐색을 줄일 수 있습니다.

해법: 백트래킹

1. 초기화: 결과 리스트 ans와 현재 부분집합 path를 준비합니다. dfs를 인덱스 0부터 호출합니다.
2. 재귀 탐색: 각 호출에서 인덱스가 배열 길이에 도달하면 현재 path를 결과에 추가합니다. 그렇지 않으면 두 분기로 나눕니다.
   • 현재 원소를 선택하지 않고 다음 인덱스로 이동
   • 현재 원소를 path에 추가하고 다음 인덱스로 이동한 뒤, 재귀가 끝나면 path에서 제거
3. 종료: 모든 분기를 탐색하면 모든 부분집합이 ans에 저장됩니다.

Java 구현

import java.util.*;

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(nums, 0, path, ans);
        return ans;
    }

    private void dfs(int[] nums, int idx, List<Integer> path, List<List<Integer>> ans) {
        if (idx == nums.length) {
            ans.add(new ArrayList<>(path));
            return;
        }

        // nums[idx]를 선택하지 않는 경우
        dfs(nums, idx + 1, path, ans);

        // nums[idx]를 선택하는 경우
        path.add(nums[idx]);
        dfs(nums, idx + 1, path, ans);
        path.remove(path.size() - 1);
    }
}

C++ 구현

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> path;
        dfs(nums, 0, path, ans);
        return ans;
    }

private:
    void dfs(const vector<int>& nums, int idx, vector<int>& path, vector<vector<int>>& ans) {
        if (idx == nums.size()) {
            ans.push_back(path);
            return;
        }

        // nums[idx]를 포함하지 않는 분기
        dfs(nums, idx + 1, path, ans);

        // nums[idx]를 포함하는 분기
        path.push_back(nums[idx]);
        dfs(nums, idx + 1, path, ans);
        path.pop_back();
    }
};

int main() {
    Solution sol;
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> result = sol.subsets(nums);

    cout << "모든 부분집합:" << endl;
    for (const auto& subset : result) {
        cout << "[ ";
        for (int value : subset) {
            cout << value << " ";
        }
        cout << "]" << endl;
    }

    return 0;
}

시간 복잡도와 공간 복잡도

• 시간 복잡도: 모든 부분집합은 2^n개이고, 각 부분집합을 결과에 복사할 때 최대 n개의 원소를 복사합니다. 따라서 O(n × 2^n)입니다.
• 공간 복잡도: 재귀 호출 깊이는 최대 n이므로 O(n)의 추가 공간이 필요합니다. 출력을 저장하는 공간은 O(n × 2^n)입니다.