'Finding all legal subsets. Backtrack Algorithm ? Dynamic Programming?

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.

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}]]

I am not sure what's a decent implementation. And what do you call this type of problem?

This is similar to parsing, which used CYK algorithm. For example if you have a sentence for Context-Free Grammar "I love you", it could follow rules {VP --> Love You, PRON --> I} and be grouped together. However, in this case, order matters. You cannot group "I" together with "you" since they are not adjacent. But in my case, this is possible, like {1,3} is grouped together.

Thank you very much



Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source