Ex-Increasing Set Sequence Background

An ex-increasing set sequence of order \$N\$ is defined as a sequence of integer sets \$S_1,S_2,\cdots,S_n\$ which satisfies the following:


Each \$S_i\$ is a non-empty subset of \$\{1,2,\cdots,N\}\$.
For \$1\le i&lt;n\$, \$S_i \cap S_{i+1} = \varnothing\$, i.e. any two consecutive sets have no elements in common.
For \$1\le i&lt;n\$, the mean (average value) of \$S_i\$ is strictly less than that of \$S_{i+1}\$.


Challenge

Given a positive integer N, output the length of the longest ex-increasing set sequence of order N.

Test cases

These are based on the results by Project Euler user thundre.

1 =&gt; 1 // {1}
2 =&gt; 2 // {1} {2}
3 =&gt; 3 // {1} {2} {3}
4 =&gt; 5 // {1} {2} {1,4} {3} {4}
5 =&gt; 7 // {1} {2} {1,4} {3} {2,5} {4} {5}
6 =&gt; 10 // {1} {2} {1,4} {3} {1,4,5} {2,3,6} {4} {3,6} {5} {6}
7 =&gt; 15 // {1} {2} {1,4} {3} {1,2,7} {3,4} {1,2,5,7} {4} {1,3,6,7} {4,5} {1,6,7} {5} {4,7} {6} {7}
8 =&gt; 21
9 =&gt; 29
10 =&gt; 39
11 =&gt; 49
12 =&gt; 63
13 =&gt; 79
14 =&gt; 99
15 =&gt; 121
16 =&gt; 145
17 =&gt; 171
18 =&gt; 203
19 =&gt; 237
20 =&gt; 277
21 =&gt; 321
22 =&gt; 369
23 =&gt; 419
24 =&gt; 477
25 =&gt; 537


Rules

Standard code-golf rules apply. The shortest valid submission in bytes wins.

Bounty

This problem has been discussed here on Project Euler forum about 4 years ago, but we failed to come up with a provable polynomial-time algorithm (in terms of N). Therefore, I will award +200 bounty to the first submission that achieves this, or prove its impossibility.
Brachylog, 28 bytes

⟦₁⊇ᶠk⊇pSs₂ᶠ{c≠&amp;⟨+/l⟩ᵐ&lt;ᵈ}ᵐ∧Sl


Try it online!

This is really damn slow. Takes about 30 seconds for N = 3, and it didn't complete after 12 minutes for N = 4. 

Explanation

⟦₁                             Take the range [1, …, Input]
  ⊇ᶠk                          Find all ordered subsets of that range, minus the empty set
     ⊇                         Take an ordered subset of these subsets
      pS                       Take a permutation of that subset and call it S
       Ss₂ᶠ                    Find all substrings of 2 consecutive elements in S
           {           }ᵐ      Map for each of these substrings:
            c≠                   All elements from both sets must be different
              &amp;⟨+/l⟩ᵐ            And the average of both sets (⟨xyz⟩ is a fork like in APL)
                     &lt;ᵈ          Must be in strictly increasing order
                         ∧Sl   If all of this succeeds, the output is the length of L.


Faster version, 39 bytes

⟦₁⊇ᶠk⊇{⟨+/l⟩/₁/₁}ᵒSs₂ᶠ{c≠&amp;⟨+/l⟩ᵐ&lt;₁}ᵐ∧Sl


This takes about 50 seconds on my computer for N = 4.

This is the same program except we sort the subset of subsets by average instead of taking a random permutation. So we use {⟨+/l⟩/₁/₁}ᵒ instead of p.

{         }ᵒ     Order by:
 ⟨+/l⟩             Average (fork of sum-divide-length)
      /₁/₁         Invert the average twice; this is used to get a float average


We need to get a float average because I just discovered a ridiculous bug in which floats and integers don't compare by value but by type with ordering predicates (this is also why I use &lt;ᵈ and not &lt;₁ to compare both averages; the latter would require that double inversion trick to work).