This question arose from a discussion between a friend and I.
$A$ is a sequence of length $T$ where for any $a_i$ in $A$, $a_i \in \left\{{1, 2, 3}\right\}$
$B$ is a sequence of length $U$ where for any $b_i$ in $B$, $b_i \in \left\{{1, 2, 3}\right\}$
And the following conditions:
1) They possess equal sum,
$N = \sum_{\forall a \in A} a = \sum_{\forall b \in B} b$
2) They don't possess sub-sequences starting at the head of equal sum,
$\sum_{i=1}^c a_i \neq \sum_{i=1}^d b_i$
for any $c < T$ and $d < U$,
where $a_i \in A$ and $b_i \in B$
Question: For given $N$, find an algorithm that calculates in polynomial time the number of possible pairs $(A, B)$ that satisfy these conditions.
It's very easy to write an algorithm that satisfies condition 1) using dynamic programming, but I simply cannot figure out how to make it satisfy 2) as well.
Good luck!