Time Complexity of 3 sum
<p>I have provided a snippet of the code for solving the 3 sum problem below.</p>

<pre><code>       int N = 10; 

  for (int i = 0; i &lt; N; i++)// this line gets executed N times
    for (int j = i+1; j &lt; N; j++)// this line gets executed N(N-1) times
      for (int k = j+1; k &lt; N; k++)// this line gets executed  N(N-1)(N-2) times
         if (a[i] + a[j] + a[k] == 0)// How many times does this line gets executed
             cnt++;
</code></pre>

<p>The textbook I am using said that the line</p>

<pre><code>if (a[i] + a[j] + a[k] == 0)
</code></pre>

<p>gets executed (N(N-1)(N-2))/6 times.
but from my analysis, the statement gets executed (N(N-1)(N-2))</p>

<p>Why is there a division by 6, whats is the proof of that.</p>