[C++] LeetCode : Subsets

Question

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

 

중복이 없는 정수 배열이 주어지면 가능한 모든 subsets(the power set)을 반환하여라.
중복된 subset이 포함되어서는 안 된다. 어떤 순서로 subset을 반환하건 상관이 없다.

 

 

제약사항

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• All the numbers of nums are unique.

---

Solution

고려사항

• 비어있는 배열이 주어졌을 때

---

Solution1 (Bruth Force)

class Solution {
public:
    void make_subset(int start, vector<vector<int>> &ans, vector<int> & curr, vector<int>& nums){
        if(start == nums.size()){
            ans.push_back(curr);
            return;
        }
		
        curr.push_back(nums[start]);
        make_subset(start+1, ans, curr, nums);
        curr.pop_back();
        make_subset(start+1, ans, curr, nums);
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> curr; 
		
        make_subset(0, ans, curr, nums);
		
        return ans;
    }
};

• Time complexity : O(N x 2ⁿ), 모든 nums를 살피는데 드는 비용 * backtrack을 위한 비용
• Space Complexity : O(N) Curr을 유지하는데 드는 공간, 나머지는 in-place에서 이루어진다.