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