fork download
copy 
  1. //
  2. //  main.cpp
  3. //  Subset Sum Using Meet in the Middle
  4. //
  5. //
  6. //
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. // Function to generate all possible subset sums
  11. void generateSubsetSums(const vector<int>& nums, vector<int>& subsetSums) {
  12.     int n = (int) nums.size();
  13.     int totalSubsets = 1 << n; // 2^n subsets
  14.  
  15.     for (int mask = 1; mask < totalSubsets; mask++) {
  16.         int sum = 0;
  17.         for (int j = 0; j < n; j++) {
  18.             if (mask & (1 << j)) { // If j-th element is in the subset
  19.                 sum += nums[j];
  20.             }
  21.         }
  22.  
  23.         subsetSums.push_back(sum);
  24.     }
  25. }
  26.  
  27. bool meetInTheMiddleSubsetSum(vector<int>& nums, int target) {
  28.     int n = (int) nums.size();
  29.     int mid = n / 2;
  30.  
  31.     // Divide the array into two halves
  32.     vector<int> left(nums.begin(), nums.begin() + mid);
  33.     vector<int> right(nums.begin() + mid, nums.end());
  34.  
  35.     // Generate all subset sums for both halves
  36.     vector<int> leftSums, rightSums;
  37.     generateSubsetSums(left, leftSums);
  38.     generateSubsetSums(right, rightSums);
  39.  
  40.     // Sort leftSums and rightSums to use binary search
  41.     sort(leftSums.begin(), leftSums.end());
  42.     sort(rightSums.begin(), rightSums.end());
  43.  
  44.     // Check if a subset sum from left half only or right half only equals target
  45.     if (binary_search(leftSums.begin(), leftSums.end(), target) ||
  46.         binary_search(rightSums.begin(), rightSums.end(), target)) {
  47.         return true;
  48.     }
  49.  
  50.     // Check if any subset sum from leftSums matches with rightSums to form target
  51.     for (int sum : leftSums) {
  52.         int required = target - sum;
  53.         if (binary_search(rightSums.begin(), rightSums.end(), required)) {
  54.             return true;
  55.         }
  56.     }
  57.  
  58.     return false;
  59. }
  60.  
  61. int main() {
  62.     vector<int> nums = {3, 4, 8, 2};
  63.     int target = 10;
  64.  
  65.     if (meetInTheMiddleSubsetSum(nums, target)) {
  66.         cout << "Subset with target sum exists" << endl;
  67.     } else {
  68.         cout << "No subset with target sum found" << endl;
  69.     }
  70.  
  71.     return 0;
  72. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Subset with target sum exists
https://ideone.com/ju1Pe5
language:
C++ 4.3.2 (gcc-4.3.2)
created:
12 hours 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!