leetcode 78) Subsets

LV. Medium 🧐

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

Subsets - LeetCode

 

문제

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.

 

Example 1:

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

Example 2:

Input: nums = [0]
Output: [[],[0]]

 

Constraints:

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

 

문제 해결법

중복되지 않게 조합을 찾아주는 문제!

재귀를 사용해서 조합을 만들어 줬다~

 

해결 코드

using namespace std;
class Solution {
private:
	vector<vector<int>>ans;
	int nums_size;

	void setComb(vector<int>comb, vector<bool>check, int idx, int size, vector<int>&nums) {
		if (idx == size)
			return ans.push_back(comb);
		for (int i = 0; i < nums_size; ++i) {
			if (check[i]) {
				comb[idx] = nums[i];
				check[i] = false;
				setComb(comb, check, idx + 1, size, nums);
			}
		}
	}
public:
	vector<vector<int>> subsets(vector<int>& nums) {
		nums_size = nums.size();
		int comb_size = 0;

		while (nums_size >= comb_size) {
			vector<int> comb(comb_size);
			vector<bool> check(nums_size, true);
			setComb(comb, check, 0, comb_size, nums);
			comb_size++;
		}
		return ans;
	}
};