fork download
copy 
  1.  
  2. #include <iostream>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. class Solution {
  7. public:
  8.     int maxOR = 0;  
  9.     int count = 0;  
  10.     vector<int> subset; 
  11.  
  12.     void solve(const vector<int>& nums, int index, int currentOR) {
  13.         if (index >= nums.size()) {
  14.             if (currentOR == maxOR) 
  15.                 count++;
  16.             return;
  17.         }
  18.  
  19.         // Do: 
  20.         subset.push_back(nums[index]);  
  21.         solve(nums, index + 1, currentOR | nums[index]); 
  22.  
  23.         // undo:
  24.         subset.pop_back();
  25.  
  26.         // recurse: 
  27.         solve(nums, index + 1, currentOR);
  28.     }
  29.  
  30.     int countMaxOrSubsets(vector<int>& nums) {
  31.         maxOR = 0;
  32.         count = 0;
  33.  
  34.  
  35.         for(int i = 0; i < nums.size(); i++)
  36.             maxOR |= nums[i]; 
  37.  
  38.         solve(nums, 0, 0); 
  39.  
  40.         return count;
  41.     }
  42. };
  43.  
  44. int main() {
  45.     Solution s;
  46.     vector<int> nums = {3,1};  
  47.     cout << "Count of subsets: " << s.countMaxOrSubsets(nums) << endl;
  48.     return 0;
  49. }
  50.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Count of subsets: 2
https://ideone.com/SP3k4o
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!