title: Reducing a N-Sum to a Two Sum
body: <p>I've recently came across a cool algorithm to reduce any problem of the sort "Find n numbers in an array that sum to a target" to a Two Sum problem. However, I am having a hard time understanding one line of the code.</p>
  
  <pre><code>def findNsum(nums, target, N, result, results):
      if len(nums) &lt; N or N &lt; 2 or target &lt; nums[0]*N or target &gt; nums[-1]*N:  # early termination
          return
      if N == 2: # two pointers solve sorted 2-sum problem
          l,r = 0,len(nums)-1
          while l &lt; r:
              s = nums[l] + nums[r]
              if s == target:
                  results.append(result + [nums[l], nums[r]])
                  l += 1
                  while l &lt; r and nums[l] == nums[l-1]:
                      l += 1
              elif s &lt; target:
                  l += 1
              else:
                  r -= 1
      else: # recursively reduce N
          for i in range(len(nums)-N+1):
              if i == 0 or (i &gt; 0 and nums[i-1] != nums[i]):
                  findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)
  
  results = []
  findNsum(sorted(nums), 0, 3, [], results)
  return results
  </code></pre>
  
  <p>The condition:</p>
  
  <pre><code>if i == 0 or (i &gt; 0 and nums[i-1] != nums[i]):
  </code></pre>
  
  <p>Does not make sense to me. Why do I have to check <code>if nums[i-1] != nums[i]</code>? If I try it out with, say, with <code>nums = [-1, 0, 1, 2, 2, -1, -4]</code>, I get <code>[[-4, 2, 2], [-1, -1, 2], [-1, 0, 1]]</code> with the condition. If I take it out I get <code>[[-4, 2, 2], [-1, -1, 2], [-1, 0, 1], [-1, 0, 1]]</code>. Can any one make sense of this?</p>
  
  <p>Cheers!</p>