Advertisement
informaticage

Partition problem

Dec 22nd, 2019
308
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.29 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_map>
  4.  
  5. bool partitionable ( std::vector <int> nums, size_t index, int currentSum, int total, std::unordered_map < std::string, bool > &MEMO );
  6. int arrSum ( std::vector <int>& arr );
  7.  
  8. int main ( void )
  9. {
  10.     std::vector <int> nums = { 23, 13, 11, 7, 6, 5, 5 };
  11.  
  12.     std::unordered_map < std::string, bool > MEMO;
  13.  
  14.     int numsSum = arrSum ( nums );
  15.  
  16.     /// IF a solution exists => sum of nums = 2k
  17.     if ( numsSum % 2 == 0 )
  18.         std::cout << partitionable ( nums, 0, 0, numsSum / 2, MEMO );
  19.     else
  20.         std::cout << false;
  21.  
  22.     return 0;
  23. }
  24.  
  25. int arrSum ( std::vector <int>& arr ) {
  26.     int sum = 0;
  27.     for ( int &element : arr )
  28.         sum += element;
  29.  
  30.     return sum;
  31. }
  32.  
  33. bool partitionable ( std::vector <int> nums, size_t index, int currentSum, int total, std::unordered_map < std::string, bool > &MEMO ) {
  34.     std::string current_item = std::to_string ( index ) + " - " + std::to_string ( currentSum );
  35.  
  36.     /// Checking if the current problem was calculated already
  37.     if ( MEMO.find ( current_item ) != MEMO.end ( ) )
  38.         return MEMO [ current_item ];
  39.  
  40.     /// Debugging
  41.     std::cout << current_item << std::endl;
  42.  
  43.     /// Problem solved :P
  44.     if ( currentSum == total ) {
  45.         MEMO[ current_item ] = true;
  46.         return true;
  47.     }
  48.  
  49.     /// Cant solve the problem anymore ( excluding negatives )
  50.     if ( currentSum > total ) {
  51.         MEMO[ current_item ] = false;
  52.         return false;
  53.     }
  54.  
  55.     /// Nothing more to add
  56.     if ( index == nums.size ( ) ) {
  57.         MEMO[ current_item ] = false;
  58.         return false;
  59.     }
  60.  
  61.     /// Checking if exists an acceptable sum after skipping the current item
  62.     bool totalWithoutCurrent =
  63.         partitionable ( nums,
  64.                        index + 1,
  65.                        currentSum,
  66.                        total, MEMO );
  67.  
  68.     /// Checking if exists an acceptable sum after adding the current item
  69.     bool totalWithCurrent =
  70.         partitionable ( nums,
  71.                        index + 1,
  72.                        currentSum + nums.at ( index ),
  73.                        total, MEMO );
  74.  
  75.     /// With our without youuuuu
  76.     bool result = totalWithCurrent or totalWithoutCurrent;
  77.     MEMO[ current_item ] = result;
  78.     return result;
  79. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement