title: How to find all partitions of a multiset (a set that allows duplicates)
body: <p>Given a collection of numbers that may contain duplicates, find all partitions of it. (all possible ways of dividing the collection.) </p>
  
  <p>For instance, the multiset {1, 1, 2} has 4 partitions:</p>
  
  <p>partition 1 = { {1}, {1}, {2} }
     partition 2 = { {1}, {1, 2} }
     partition 3 = { {1, 1}, {2} }
     partition 4 = { {1, 1, 2} }</p>
  
  <p>Here is a similar question <a href="https://stackoverflow.com/questions/20530128/how-to-find-all-partitions-of-a-set">How to find all partitions of a set</a> but in that question, all numbers are distinct. </p>
  
  <p>Definition for set partitions: <a href="https://en.wikipedia.org/wiki/Partition_of_a_set" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Partition_of_a_set</a></p>
  
  <p>Definition for multiset： <a href="https://en.wikipedia.org/wiki/Multiset" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Multiset</a></p>
  
  <p>A solution written in any common programming language with some explanation will be greatly appreciated. </p>
  
  <hr>
  
  <p>Update：  </p>
  
  <p>Seems like a lot of people are confused what the question is asking about. It's <strong>NOT</strong> asking for all the possible subsets of the given collection. Rather, it's asking you to find out all the different ways of dividing the given collection of numbers.  </p>