Company: Goldman Sachs OA
Difficulty: medium
3. Set Partitioning Given a set containing integers, find the number of possible ways to partition the set into non-empty subsets such that the union of these subsets yields the original set. A valid partition divides the input set into two or more non-empty subsets. Each subset must contain at least one element from the input, and the union of all subsets in the partition should be exactly the original input set. For a set {x, y, z}, a valid partition must divide it into two or more non-empty subsets whose union equals {x, y, z}. The partition {x, y, z} alone is not valid because it doesn't divide the set—it just contains the entire set as one piece. Valid partitions of {x, y, z} include: {[x], [y], [z]} {[x, y], [z]} {[x, z], [y]} {[y, z], [x]} Each of these has at least two non-empty subsets and the union of these subsets creates the original set. Input Format A single line of input contains a set of integers, where the integers are separated by single whitespaces. Output Format A s