title: Given an array A of size N, find all combination of four elements in the array whose sum is equal to a given value K
body: <p>Given an array A of size N, find all combinations of four elements in the array whose sum is equal to a given value K. For example, if the given array is {10, 2, 3, 4, 5, 9, 7, 8} and K = 23, one of the quadruple is “3 5 7 8” (3 + 5 + 7 + 8 = 23).</p>
  
  <p>The output should contain only unique quadruple For example, if the input array is {1, 1, 1, 1, 1, 1} and K = 4, then the output should be only one quadruple {1, 1, 1, 1}</p>
  
  <p><strong>My approach:</strong> I tried to solve this problem by storing all the distinct pairs formed from the given array into a hash table (<code>std::unordered_multimap</code>), with their sum as key. Then for each pair sum, I looked for (K - sum) key in the hash table. The problem with this approach is I am getting too many duplicated like (i, j, l, m) and (i, l, j, m) are the same, plus there are duplicates due to the same items in the array. I am not sure what is the optimal way to address that.</p>
  
  <p>The code for the above-mentioned approach is:</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;unordered_map&gt;
  #include &lt;tuple&gt;
  #include &lt;vector&gt;
  
  
  int main() {
      size_t tc = 0;
      std::cin &gt;&gt; tc; //number of test cases
      while(tc--) {
          size_t n = 0, k = 0;
          std::cin &gt;&gt; n &gt;&gt; k;
          std::vector&lt;size_t&gt; vec(n);
          for (size_t i = 0; i &lt; n; ++i)
              std::cin &gt;&gt; vec[i];
  
          std::unordered_multimap&lt;size_t, std::tuple&lt;size_t, size_t&gt;&gt; m;
          for (size_t i = 0; i &lt; n - 1; ++i)
          for (size_t j = i + 1; j &lt; n; ++j) {
              const auto sum = vec[i] + vec[j];
              m.emplace(sum, std::make_tuple(i, j));
          }
  
          for (size_t i = 0; i &lt; n - 1; ++i)
          for (size_t j = i + 1; j &lt; n; ++j) {
              const auto sum = vec[i] + vec[j];
              auto r = m.equal_range(k - sum);
              for (auto it = r.first; it != r.second; ++it) {
                  if ((i == std::get&lt;0&gt;(it-&gt;second))
                  ||(i == std::get&lt;1&gt;(it-&gt;second))
                  ||(j == std::get&lt;0&gt;(it-&gt;second))
                  || (j == std::get&lt;1&gt;(it-&gt;second)))
                  continue;
                  std::cout &lt;&lt; vec[i] &lt;&lt; ' ' &lt;&lt; vec[j] &lt;&lt; ' ' 
                  &lt;&lt; vec[std::get&lt;0&gt;(it-&gt;second)] &lt;&lt; ' '
                  &lt;&lt; vec[std::get&lt;1&gt;(it-&gt;second)] &lt;&lt; '$';
              }
  
              r = m.equal_range(sum);
              for (auto it = r.first; it != r.second; ++it) {
                  if ((i == std::get&lt;0&gt;(it-&gt;second))
                  &amp;&amp; (j == std::get&lt;1&gt;(it-&gt;second))) {
                      m.erase(it);
                      break;
                  }
              }
          }
  
          std::cout &lt;&lt; '\n';
      }
      return 0;
  }
  </code></pre>
  
  <p>The above code will run as-is in the link mentioned below in the Note.</p>
  
  <p>Note: This problem is taken from <a href="https://practice.geeksforgeeks.org/problems/find-all-four-sum-numbers/0" rel="nofollow noreferrer">https://practice.geeksforgeeks.org/problems/find-all-four-sum-numbers/0</a></p>