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();
        }
    }
};