title: Two Sum and its Time Complexity
body: <p>I was going over both solutions to <a href="https://leetcode.com/problems/two-sum/" rel="nofollow noreferrer">Two Sum</a> on leetcode and I noticed that the n^2 solution is to basically test all combinations of two numbers and see if they sum to Target.</p>
  <p>I understand the naive solution iterates over each element of the array( or more precisely n-1 times because we can't compare the last element to itself) to grab the first addend and then another loop to grab all of the following elements. This second loop needs to iterate n-1-i times where i is the index of the first addend. I can  see that (n-1)(n-1-i) is O(n^2).</p>
  <p>The problem comes when I googled &quot;algorithm for finding combinations&quot; and it lead to <a href="https://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n">this</a> thread where the accepted answer talks about Gray Codes which goes way above my head.</p>
  <p>Now I'm unsure whether my assumption was correct, the naive solution is a version of a Gray Code, or something else.</p>
  <p>If Two Sum is a combinations problem then it's Time Complexity would be O(n!/ ((n-k)! k!)) or O(nCk) but I don't see how that reduces to O(n^2)</p>