Tập con II trong C ++

Giả sử chúng ta có một bộ số; chúng ta phải tạo tất cả các tập con có thể có của tập hợp đó. Đây còn được gọi là bộ nguồn. Chúng tôi phải ghi nhớ rằng các phần tử có thể bị trùng lặp. Vì vậy, nếu tập hợp giống như [1,2,2], thì tập hợp lũy thừa sẽ là [[], [1], [2], [1,2], [2,2], [1,2,2 ]]

Hãy để chúng tôi xem các bước -

• Xác định một res mảng và một tập hợp khác được gọi là x
• Chúng tôi sẽ giải quyết vấn đề này bằng cách sử dụng phương pháp đệ quy. Vì vậy, nếu tên phương thức đệ quy được gọi là giải quyết () và điều này nhận chỉ số, một mảng tạm thời và mảng số (num)
• Hàm giải quyết () sẽ hoạt động như bên dưới -
• if index =size of v, then
  • nếu tạm thời không có trong x, thì hãy chèn tạm thời vào res và cũng chèn tạm thời vào x
  • trở lại
• gọi giải quyết (chỉ mục + 1, tạm thời, v)
• chèn v [index] vào tạm thời
• gọi giải quyết (chỉ mục + 1, tạm thời, v)
• loại bỏ phần tử cuối cùng khỏi tạm thời
• Chức năng chính sẽ giống như bên dưới -
• xóa res và x, đồng thời sắp xếp mảng đã cho, xác định nhiệt độ mảng
• gọi giải quyết (0, tạm thời, mảng)
• sắp xếp mảng res và trả về res

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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

Đầu vào

[1,2,2]

Đầu ra

[[],[1, ],[1, 2, ],[1, 2, 2, ],[2, ],[2, 2, ],]