title: Coin change with split into two sets
body: <p>I'm trying to figure out how to solve a problem that seems a tricky variation of a common algorithmic problem but require additional logic to handle specific requirements.</p>
  
  <p>Given a list of coins and an amount, I need to count the total number of possible ways to extract the given amount using an unlimited supply of available coins (and this is a classical change making problem <a href="https://en.wikipedia.org/wiki/Change-making_problem" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Change-making_problem</a> easily solved using dynamic programming) <strong>that also satisfy some additional requirements</strong>:</p>
  
  <ul>
  <li>extracted coins are splittable into two sets of equal size (but not necessarily of equal sum)</li>
  <li>the order of elements inside the set doesn't matter but the order of set does.</li>
  </ul>
  
  <p><strong>Examples</strong></p>
  
  <p>Amount of 6 euros and coins [1, 2]: solutions are 4</p>
  
  <pre><code>[(1,1), (2,2)]
  [(1,1,1), (1,1,1)]
  [(2,2), (1,1)]
  [(1,2), (1,2)]
  </code></pre>
  
  <p>Amount of 8 euros and coins [1, 2, 6]: solutions are 7</p>
  
  <pre><code>[(1,1,2), (1,1,2)]
  [(1,2,2), (1,1,1)]
  [(1,1,1,1), (1,1,1,1)]
  [(2), (6)]
  [(1,1,1), (1,2,2)]
  [(2,2), (2,2)]
  [(6), (2)]
  </code></pre>
  
  <p>By now I tried different approaches but the only way I found was to collect all the possible solution (using dynamic programming) and then filter non-splittable solution (with an odd number of coins) and duplicates. I'm quite sure there is a combinatorial way to calculate the total number of duplication but I can't figure out how.</p>