Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <unordered_map>
- bool partitionable ( std::vector <int> nums, size_t index, int currentSum, int total, std::unordered_map < std::string, bool > &MEMO );
- int arrSum ( std::vector <int>& arr );
- int main ( void )
- {
- std::vector <int> nums = { 23, 13, 11, 7, 6, 5, 5 };
- std::unordered_map < std::string, bool > MEMO;
- int numsSum = arrSum ( nums );
- /// IF a solution exists => sum of nums = 2k
- if ( numsSum % 2 == 0 )
- std::cout << partitionable ( nums, 0, 0, numsSum / 2, MEMO );
- else
- std::cout << false;
- return 0;
- }
- int arrSum ( std::vector <int>& arr ) {
- int sum = 0;
- for ( int &element : arr )
- sum += element;
- return sum;
- }
- bool partitionable ( std::vector <int> nums, size_t index, int currentSum, int total, std::unordered_map < std::string, bool > &MEMO ) {
- std::string current_item = std::to_string ( index ) + " - " + std::to_string ( currentSum );
- /// Checking if the current problem was calculated already
- if ( MEMO.find ( current_item ) != MEMO.end ( ) )
- return MEMO [ current_item ];
- /// Debugging
- std::cout << current_item << std::endl;
- /// Problem solved :P
- if ( currentSum == total ) {
- MEMO[ current_item ] = true;
- return true;
- }
- /// Cant solve the problem anymore ( excluding negatives )
- if ( currentSum > total ) {
- MEMO[ current_item ] = false;
- return false;
- }
- /// Nothing more to add
- if ( index == nums.size ( ) ) {
- MEMO[ current_item ] = false;
- return false;
- }
- /// Checking if exists an acceptable sum after skipping the current item
- bool totalWithoutCurrent =
- partitionable ( nums,
- index + 1,
- currentSum,
- total, MEMO );
- /// Checking if exists an acceptable sum after adding the current item
- bool totalWithCurrent =
- partitionable ( nums,
- index + 1,
- currentSum + nums.at ( index ),
- total, MEMO );
- /// With our without youuuuu
- bool result = totalWithCurrent or totalWithoutCurrent;
- MEMO[ current_item ] = result;
- return result;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement