fork download
copy 
  1. #include <iostream>
  2. #include <unordered_map>
  3.  
  4. using namespace std;
  5.  
  6. const int N = 50;
  7. int a[50][4]= {{0, 1, -1, 0},
  8.           {1, -1, 0, 0},
  9.           {-1, 1, 0, -1}};
  10. /*
  11. int a[50][4]= {{0, 1, 1, 0},
  12.           {1, 1, 0, 0},
  13.           {1, 1, 0, 1}};
  14.           */
  15.  
  16. unordered_map<int, bool> dp[N];
  17.  
  18. int hashsum(int sum1, int sum2, int sum3, int sum4) {
  19.   int offset = N;
  20.   int base = 2 * N;
  21.   int hashSum = 0;
  22.   hashSum += (sum1 + offset) * 1;
  23.   hashSum += (sum2 + offset) * base;
  24.   hashSum += (sum3 + offset) * base * base;
  25.   hashSum += (sum4 + offset) * base * base * base;
  26.   return hashSum;
  27. }
  28.  
  29. bool subset(int n, int sum1, int sum2, int sum3, int sum4)
  30. {
  31.   // Base case: No tuple selected
  32.   if (n == -1  && !sum1 && !sum2 && !sum3 && !sum4)
  33.     return true;
  34.   // Base case: No tuple selected with non-zero sum
  35.   else if(n == -1)
  36.     return false;
  37.   else if(dp[n].find(hashsum(sum1, sum2, sum3, sum4)) != dp[n].end() )
  38.     return dp[n][hashsum(sum1, sum2, sum3, sum4)];
  39.  
  40.   // Include the current element
  41.   bool include = subset(n - 1,
  42.     sum1 - a[n][0],
  43.     sum2 - a[n][1],
  44.     sum3 - a[n][2],
  45.     sum4 - a[n][3]);
  46.   // Exclude the current element
  47.   bool exclude = subset(n - 1, sum1, sum2, sum3, sum4);
  48.  
  49.   return dp[n][hashsum(sum1, sum2, sum3, sum4)] = include || exclude;
  50. }
  51.  
  52. int main()
  53. {
  54.   int n = 3;
  55.   bool flag = false;
  56.   int sum1, sum2, sum3, sum4;
  57.   for (sum1 = -n; sum1 <= 0; sum1++) {
  58.     for (sum2 = -n; sum2 <= 0; sum2++) {
  59.       for (sum3 = -n; sum3 <= 0; sum3++) {
  60.         for (sum4 = -n; sum4 <= 0; sum4++) {
  61.           if (subset(n - 1, sum1, sum2, sum3, sum4)) {
  62.             flag = true;
  63.             goto done;
  64.           }
  65.         }
  66.       }
  67.     }
  68.   }
  69.   done:
  70.   if (flag && (sum1 || sum2 || sum3 || sum4))
  71.     cout << "Solution found. " << sum1 << ' ' << sum2 << ' ' << sum3 << ' ' << sum4 << std::endl;
  72.   else
  73.     cout << "No solution found.\n";
  74.   return 0;
  75. }
  76.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Solution found. 0 0 0 -1
https://ideone.com/AeCf14
language:
C++ (gcc 8.3)
created:
6 years 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!