Giả sử chúng ta có một tập hợp các số; chúng ta phải tạo ra tất cả các tập con có thể của tập hợp đó. Đây còn gọi là tập hợp lũy thừa (power set). Lưu ý rằng các phần tử có thể trùng lặp. Ví dụ, nếu tập hợp là [1,2,2], thì tập lũy thừa sẽ là [[], [1], [2], [1,2], [2,2], [1,2,2]]
Các bước thực hiện:
- Định nghĩa mảng res và tập hợp x
- Giải quyết bằng đệ quy. Hàm đệ quy solve() nhận chỉ số, mảng tạm, và mảng số (nums)
- Hàm solve() hoạt động như sau:
- nếu index = kích thước v
- nếu temp không có trong x, thêm temp vào res và thêm temp vào x
- return
- gọi solve(index + 1, temp, v)
- thêm v[index] vào temp
- gọi solve(index + 1, temp, v)
- xóa phần tử cuối của temp
- Hàm main:
- xóa res và x, sắp xếp mảng cho trước, định nghĩa mảng temp
- gọi solve(0, temp, array)
- sắp xếp res và return res
Hãy xem 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)); }Input
[1,2,2]
Output
[[],[1, ],[1, 2, ],[1, 2, 2, ],[2, ],[2, 2, ],]