Necklace splitting problem Background

I was inspired by 3Blue1Brown's recent video about the necklace splitting problem (or as he calls it, the stolen necklace problem) and its relationship to the Borsuk-Ulam theorem.

In this problem, two thieves have stolen a valuable necklace consisting of several different types of jewels. There are an even number of each type of jewel and the thieves wish to split each jewel type evenly amongst the two of them. The catch is that they must do so by splitting the necklace into some number of contiguous segments and distribute the segments between the two of them.

Here is an example with four jewel types denoted S, E, D, and R (for sapphire, emerald, diamond, and ruby, respectively). Let's say the necklace is as follows:

[S,S,S,E,S,D,E,R,S,R,E,S,S,S,D,R,E,E,R,E,D,E,R,R,D,E,E,E]


There are 8 sapphires, 10 emeralds, 4 diamonds, and 6 rubies. We can split the necklace as follows:

[[S],[S],[S,E,S,D,E,R,S],[R,E,S,S,S,D,R,E,E,R,E,D,E],[R,R,D,E,E,E]]


Then if we give the first, third, and fifth segments to one thief and the second and fourth segments to the other thief, each will end up with 4 sapphires, 5 emeralds, 2 diamonds, and 3 rubies:

[S],    [S,E,S,D,E,R,S],                            [R,R,D,E,E,E]
    [S],                [R,E,S,S,S,D,R,E,E,R,E,D,E],


Using 0-indexing, these cuts occur at the indices [1,2,9,22]. 

Goal

It turns out that such a fair division can always be done using at most n cuts, where n is the number of jewel types. Your task is to write a complete program or function which takes a necklace as input and outputs a minimal such division (fewest number of cuts).

Input

Input may be in any convenient format. The necklace should be a sequence of jewels and nothing more; e.g. a list of integers, dictionary with keys representing the jewel types and values being lists of indices. You may optionally include the length of the necklace or the number of distinct jewel types, but you should not take any other input. 

You may assume that the input necklace is valid. You do not need to handle the case where there is an odd number of jewels of a given type or the necklace is empty.

Output

Again, output may be in any convenient format; e.g. a list of segments, a list of cut positions, a dictionary with keys representing the two thieves and values being lists of segments, etc. Segments may be represented by their starting index, ending index, list of consecutive indices, list of jewels, their lengths, etc. You may use 0- or 1- indexing. If the ordering is not significant to your format, then your output may be in any order. Here is the above output in several different formats:

list of segments: [[S],[S],[S,E,S,D,E,R,S],[R,E,S,S,S,D,R,E,E,R,E,D,E],[R,R,D,E,E,E]]
list of cuts:     [1,2,9,22]
list of lengths:  [1,1,7,13,6]
dictionary:       {'thief1' : [(R,R,D,E,E,E),(S),(S,E,S,D,E,R,S)], 'thief2' : [(S),(R,E,S,S,S,D,R,E,E,R,E,D,E)]}


Note that order is important in the list of segments (segments alternate between the thieves) and the list of lengths (in order to identify the segments), but not in the list of cuts or the dictionary. Edit: Greg Martin pointed out that these wouldn't be valid outputs since a fair division can be obtained in two cuts

Test cases

[1,2,1,2,1,3,1,3,3,2,2,3] -&gt; [[1,2,1],[2,1,3,1],[3,3,2],[2,3]]
[1,1,1,1,2,2,3,3,3,3,3,3] -&gt; [[1,1],[1,1,2],[2,3,3,3],[3,3,3]]
[1,1,1,1,1,1,1,1,1,1,1,1] -&gt; [[1,1,1,1,1,1],[1,1,1,1,1,1]]
[1,1,1,1,2,3,4,2,3,4,2,2] -&gt; [[1,1],[1,1,2,3,4,2],[3,4,2,2]]


Notes


Standard loopholes are forbidden.
This is code-golf; shortest answer (in bytes) wins.
Jelly, 18 bytes
s2ZFṢ$€E¬,L
ŒṖṖÇÞḢ

Try it online!
Not efficient - the example has 28 jewels which wont work without huge resources since this implementation's first step would be to build a list of the 227 possible partitions.
Returns a list of lists - the segments in the order to dish them out between alternate thieves. (Re the TIO output: when a list only has a single item the implicit print does not bother with the brackets, [])
How?
s2ZFṢ$€E¬,L - Link 1, get (isUnfair, Slices): A possible partition
s2          - split into slices of length 2 (any odd one on it's own at the end)
  Z         - transpose (first item is one thief's slices, second is the others)
     $€     - last two links as a monad for €ach
   F        -     flatten
    Ṣ       -     sort
       E    - equal? (theif1's jewels == theif2's jewels)
        ¬   - not
          L - length (number of slices in the partition)
         ,  - pair

ŒṖṖÇÞḢ - Main link: necklace
ŒṖ     - all partitions
  Ṗ    - pop, we must remove the rightmost one...
              because Link 1 will say it is fair, and it will have length 1!
              (a list of one thing has all entries equal)
    Þ  - sort by
   Ç   -     last link (1) as a monad
     Ḣ - head (get the first one, i.e. minimal isUnfair, then minimal length)