# #StackBounty: #combinatorics #fastest-code Count arrays that are really unique

### Bounty: 50

This is a follow up to Count arrays that make unique sets . The significant difference is the definition of uniqueness.

Consider an array `A` of length `n`. The array contains only positive integers. For example `A = (1,1,2,2)`. Let us define `f(A)` as the set of sums of all the non-empty contiguous subarrays of `A`. In this case `f(A) = {1,2,3,4,5,6}`. The steps to produce `f(A)` are as follows:

The subarrays of `A` are `(1), (1), (2), (2), (1,1), (1,2), (2,2), (1,1,2), (1,2,2), (1,1,2,2)`. Their respective sums are `1,1,2,2,2,3,4,4,5,6`. The set you get from this list is therefore `{1,2,3,4,5,6}`.

We call an array `A` unique if there is no other array `B` of the same length such that `f(A) = f(B)`, except for the array `A` reversed. As an example, `f((1,2,3)) = f((3,2,1)) = {1,2,3,5,6}` but there is no other array of length `3` that produces the same set of sums.

The task, for a given `n` and `s` is to count the number of unique arrays of that length. You can assume that `s` is between `1` and `9`. You only need to count arrays where the elements are either a given integer `s` or `s+1`. E.g. if `s=1` the arrays you are counting only contain `1` and `2`. However, the definition of uniqueness is with respect to any other array of the same length. As a concrete example `[1, 2, 2, 2]` is not unique as it gives the same set of sums as `[1, 1, 2, 3]`.

You should count the reverse of an array as well as the array itself (as long as the array is not a palindrome of course).

Examples

`s = 1`, the answers for n = 2,3,4,5,6,7,8,9 are:

``````4, 3, 3, 4, 4, 5, 5, 6
``````

For `s = 1`, the unique arrays of length 4 are

``````(1, 1, 1, 1)
(2, 1, 1, 2)
(2, 2, 2, 2)
``````

`s = 2`, the answers for n = 2,3,4,5,6,7,8,9 are:

``````4, 8, 16, 32, 46, 69, 121, 177
``````

An example of an array that is not unique with `s = 2` is:

``````(3, 2, 2, 3, 3, 3).
``````

This has the same set of sums as both of: `(3, 2, 2, 2, 4, 3)` and `(3, 2, 2, 4, 2, 3)`.

`s = 8`, the answers for n = 2,3,4,5,6,7,8,9 are:

``````4, 8, 16, 32, 64, 120, 244, 427
``````

Score

For a given `n`, your code should output the answer for all values of `s` from `1` to `9`. Your score is the highest value of `n` for which this completes in one minute.

Testing

I will need to run your code on my ubuntu machine so please include as detailed instructions as possible for how to compile and run your code.