title: Uva 10364 Tell if it is possible to use sticks of varying lengths to make a square
body: <p>I have been stuck on <a href="http://uva.onlinejudge.org/external/103/10364.html" rel="nofollow">this uva problem</a> from a long time now. </p>
  
  <p>Abridged problem statement : Given a set of sticks of various lengths, is it possible to join them end-to-end to form a square? There are a maximum of 20 sticks and each stick has a length less than 10000.</p>
  
  <p>There are different solutions possible for this problem. One of them is a backtracking solution explained <a href="http://amrfeldfrawy.wordpress.com/2013/07/11/uva-10364-square/" rel="nofollow">here</a>. But there exists other dynamic programming solutions explained <a href="http://f0rth3r3c0rd.wordpress.com/2011/10/12/uva-10364-square/" rel="nofollow">here</a>, <a href="http://ajmarin.alwaysdata.net/codes/problems/989/" rel="nofollow">here</a> and <a href="http://kaikaiw321.blogspot.in/2013/09/uva-10364.html" rel="nofollow">here</a> with a better running time. But I can't understand what approach they are using. Please help me understand the dp algorithm.</p>