숫자 집합이 있다고 가정합니다. 우리는 그 집합의 가능한 모든 부분집합을 생성해야 합니다. 이를 전원 세트라고도 합니다. 요소가 중복될 수 있음을 명심해야 합니다. 따라서 집합이 [1,2,2]와 같으면 거듭제곱 집합은 [[], [1], [2], [1,2], [2,2], [1,2,2 ]]
단계를 살펴보겠습니다 -
- 하나의 배열 res와 x라는 다른 집합을 정의합니다.
- 재귀적 접근 방식을 사용하여 이 문제를 해결할 것입니다. 따라서 재귀 메서드 이름이 solve()라고 하고 인덱스, 임시 배열 1개, 숫자 배열(nums)을 사용하는 경우
- solve() 함수는 아래와 같이 작동합니다 -
- 인덱스 =v의 크기이면
- temp가 x에 없으면 res에 temp를 삽입하고 x에도 temp를 삽입합니다.
- 반환
- solve(index + 1, temp, v) 호출
- v[index]를 temp에 삽입
- solve(index + 1, temp, v) 호출
- temp에서 마지막 요소 제거
- 주요 기능은 아래와 같습니다 -
- res와 x를 지우고 주어진 배열을 정렬하고 배열 temp를 정의합니다.
- 해결(0, 임시, 배열) 호출
- res 배열을 정렬하고 res를 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<int> > v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
class Solution {
public:
vector < vector <int> > res;
set < vector <int> > x;
static bool cmp(vector <int> a, vector <int> b){
return a < b;
}
void solve(int idx, vector <int> temp, vector <int> &v){
if(idx == v.size()){
if(x.find(temp) == x.end()){
res.push_back(temp);
x.insert(temp);
}
return;
}
solve(idx+1, temp, v);
temp.push_back(v[idx]);
solve(idx+1, temp, v);
temp.pop_back();
}
vector<vector<int> > subsetsWithDup(vector<int> &a) {
res.clear();
x.clear();
sort(a.begin(), a.end());
vector <int> temp;
solve(0, temp, a);
sort(res.begin(), res.end(), cmp);
return res;
}
};
main(){
Solution ob;
vector<int> v = {1,2,2};
print_vector(ob.subsetsWithDup(v));
} 입력
[1,2,2]
출력
[[],[1, ],[1, 2, ],[1, 2, 2, ],[2, ],[2, 2, ],]