LeetCode 78 - Subsets (Medium)

출처: https://leetcode.com/problems/subsets/

// LeetCode 78 - Subsets (Medium)
// https://leetcode.com/problems/subsets/

// 문제 설명
// unique 원소로 이루어진 정수 배열 nums가 주어진다.
// nums의 모든 가능한 부분집합(power set)을 반환하라.
// 결과에 중복 부분집합이 있어선 안 되며, 어떤 순서로 반환해도 무방하다.

// 제약 조건
// 1 <= nums.length <= 10
// -10 <= nums[i] <= 10
// nums의 모든 원소는 unique

// Example 1
// Input : nums = [1,2,3]
// Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]   (총 2^3 = 8개)
//
// Example 2
// Input : nums = [0]
// Output: [[],[0]]


#include <vector>
using namespace std;

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

private:
    void backtrack(const vector<int>& nums, int start,
                   vector<int>& path, vector<vector<int>>& out)
    {
        out.push_back(path);
        for (int i = start; i < (int)nums.size(); ++i)
        {
            path.push_back(nums[i]);
            backtrack(nums, i + 1, path, out);
            path.pop_back();
        }
    }
};

핵심 요약 — 부분집합 백트래킹은 재귀 진입 시점마다 현재 path를 답에 넣는다 — 리프에서만 답이 나오는 순열과 달리 탐색 트리의 모든 노드가 곧 하나의 부분집합이다. start 인덱스로 항상 앞으로만 나아가게 해서 중복을 차단한다.