[leetcode 78] Subsets

Given a set of distinct integers, nums, return all possible subsets (the power set).

 

가능한 모든 부분집합을 구하라.

 

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3] Output: [ [3],   [1],   [2],   [1,2,3],   [1,3],   [2,3],   [1,2],   [] ]

 

풀이:

전형적인 백트래킹 문제이다.

cnt가 nums길이와 같아지면 종료하지만 그 전에 만들어지는 모든 경우의 수 역시 정답에 저장한다.

class Solution {
public:
    vector<vector<int>> result;

    void BackTracking(int cnt, int idx, vector<int>& v, vector<int> &nums){
        if(cnt == nums.size()+1){
            return;
        }
        
        result.push_back(v);
        for(int i = idx; i<nums.size(); i++){
            v.push_back(nums[i]);
            BackTracking(cnt+1, i+1, v, nums);
            v.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<int> tmp;
        BackTracking(0,0,tmp,nums);
        return result;
    }
};