Let's denote the family of sets that have the partition located at index ~k~ as ~A_k~, and the family of all possible initial sets as ~X~.

Then the solution is all sets from ~X \setminus \bigcup_{i=1}^N A_i~.

The inclusion-exclusion principle provides us with an efficient way of calculating the size of the solution set. It holds:

$$\displaystyle \left|X \setminus \bigcup_{i=1}^N A_i\right| = \sum_{S \subseteq \{1, 2, \dots, N\}} (-1)^{|S|} \left|\bigcap_{i \in S} A_i\right|$$

In order to calculate the cardinality of the required intersection, we need to count how many pairings such that the partitions are located at ~S~. We are not interested in partitions at other locations.

That number is equal to ~2^t~, where ~t~ is the total number of pairs that don't "cross over" any partition location. The time complexity of this solution is ~\mathcal O(2^N \times N)~.

Please note: A solution using dynamic programming also exists and is left as an exercise to the reader.