title: Handling duplicated array elements
body: <p>I am in trouble handling duplicated elements in arrays. For example, in the problem of finding all pairs of integers within an array which sum to a specified value, here is my implementation:</p>
  
  <pre><code>vector&lt;pair&lt;int, int&gt;&gt; find_all_pairs_with_sum(int data[], int length, int sum)
  {
      assert(data &amp;&amp; length&gt;1);
  
      vector&lt;pair&lt;int, int&gt;&gt; res;
  
      sort(data, data+length);
  
      int first = 0; 
      int last = length - 1; 
      while (first &lt; last) 
      { 
          int s = data[first] + data[last]; 
          if (s == sum) 
          {
              res.push_back(make_pair(data[first], data[last]));
  
              ++first; 
              --last; 
          } 
          else 
          { 
              if (s &lt; sum)
                  ++first; 
              else
                  --last; 
          } 
      } 
  
      return res;
  }
  </code></pre>
  
  <p>The problem will occur when the array contains duplicated elements. For example, when </p>
  
  <pre><code>int data[] = {3, 4, 3, 4};
  int sum = 7;
  </code></pre>
  
  <p>The program will only give two pairs <code>(3,4) (3,4)</code>. However, in this case, the correct answer should be four pairs <code>(3,4) (3,4) (3,4) (3,4)</code> (as 4=2x2). How can I modify the code  in order to correctly handle such cases (hopefully still in <code>O(n logn)</code>)? It seems the change should be made in <code>if (s==sum)</code> scope while updating <code>first</code> and <code>last</code>, but I just cannot make it right.</p>
  
  <p><em>Note that: I know another way that can handle this correctly by using a <code>hash table</code> to record occurrences of each elements. Please suggest how to work through this problem without using a <code>hash table</code>.</em>  </p>