title: Recover original array from all subsets
body: <p>You are given all subset sums of an array. You are then supposed to recover the original array from the subset sums provided. </p>
  
  <p>Every element in the original array is guaranteed to be non-negative and less than 10^5. There are no more than 20 elements in the original array. The original array is also sorted.  The input is guaranteed to be valid. </p>
  
  <p><strong>Example 1</strong></p>
  
  <p>If the subset sums provided are this:</p>
  
  <pre><code>0 1 5 6 6 7 11 12
  </code></pre>
  
  <p>We can quickly deduce that the size of the original array is 3 since there are 8 (2^3) subsets. The output (i.e original array) for the above input is this:</p>
  
  <pre><code>1 5 6
  </code></pre>
  
  <p><strong>Example 2</strong></p>
  
  <p>Input:</p>
  
  <pre><code>0 1 1 2 8 9 9 10
  </code></pre>
  
  <p>Output:</p>
  
  <pre><code>1 1 8
  </code></pre>
  
  <p><strong>What I Tried</strong></p>
  
  <p>Since all elements are guaranteed to be non-negative, the largest integer in the input must be the total of the array. However, I am not sure as to how do I proceed from there. By logic, I thought that the next (2^2 - 1) largest subset sums must include all except one element from the array.</p>
  
  <p>However, the above logic does not work when the original array is this:</p>
  
  <pre><code>1 1 8
  </code></pre>
  
  <p>That's why I am stuck and am not sure on how to proceed on.</p>