title: Finding all legal subsets. Backtrack Algorithm ? Dynamic Programming?
body: <p>I am confused about the implementation of the following problem.
  I have a bag of items, and a bag of rules specifying which items could be grouped together.</p>
  <pre><code>Items [1,2,3]
  Rules [{1,2}, {3}, {1,3}, {2}, {1}, {1,2,3,4,5}]
  
  Example output
  [[{1,2},{3}], [{1,3}, {2}], [{1},{2},{3}]]
  </code></pre>
  <p>I am not sure what's a decent implementation. And what do you call this type of problem?</p>
  <p>This is similar to parsing, which used CYK algorithm. For example if you have a sentence for Context-Free Grammar &quot;I love you&quot;, it could follow rules {VP --&gt; Love You, PRON --&gt; I} and be grouped together. However, in this case, order matters. You cannot group &quot;I&quot; together with &quot;you&quot; since they are not adjacent. But in my case, this is possible, like {1,3} is grouped together.</p>
  <p>Thank you very much</p>