title: Recursively determine whether elements in array can sum to target - C++
body: <p>I am doing practice with recursion and trying small problems. One of the functions I am trying to design <code>comboSum</code> takes in an array of integers, its size, and a target value. It returns true if a combination of any of the elements (can only use each element once) adds to the target value. This is my implementation so far.</p>
  
  <pre><code>// Expected Behaviors
  // comboSum([1, 2, 3], 3, 0) =&gt; false
  // comboSum([2, 4, 8], 3, 12) =&gt; true
  // comboSum([2, 4, 8], 3, 11) =&gt; false
  // comboSum([], 0, 0) =&gt; true
  
  bool comboSum(const int a[], int size, int target)
  {
      if (target == 0)
          return true; // if we have decremented target to zero
      if (target != 0 &amp;&amp; size == 0)
          return false; // if we havent hit target to zero and we have no more elements
  
      size--;
  
      return (comboSum(a, size, target) || comboSum(a, size, target - a[size]));
  
      // OR logic ensures that even if just one sum exists, this returns true
  }
  </code></pre>
  
  <p>My algorithm works except for the case of an array with all non-zero values and the target being zero. The function immediately returns true without checking for a valid summation.</p>
  
  <pre><code>// comboSum({1, 2, 3}, 3, 0) returns true when this should be false
  </code></pre>
  
  <p>What are some possible ways to correct this issue?</p>
  
  <p><strong>Edit:</strong> I cannot change the parameters or call any additional helper functions. The function header must remain as is and I must solve the problem recursively (no use of for or while loops or STL algorithms)</p>