Find two sequences of integers that have sum N but that don't have sub-sequences starting at the head of equal sum 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 &lt; T$ and $d &lt; 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!
You can solve this with dynamic programming as well.

To see this, first realize you can see this problem as splitting the numbers between $0$ and $N$ into two subsets $X$ and $Y$ (the cumulative sums) that cannot overlap except at $0$ and $N$ (and must overlap there), and where the difference between consecutive elements of a subset is at most 3.

Reformulating the problem this way, you can have the state of your dynamic programming be:

"The number of ways of splitting the numbers between $0$ and $i-1$ into two sequences in the fashion described in the second paragraph, where the the numbers in positions (i, i-1, i-2) have assignments (j,k,h)", with $3 \leq i \leq N-1$, and $(j,k,h) \in \{X,Y,None\}$.

Using the states for $i=k$ to compute the states for $i=k+1$, it does take $\Theta(N)$ time to compute this. Let me know if more details are required.

Edit: I had missed in the previous answer the fact that $T$ and $U$ are fixed. You can take care of this by adding in your state how many positions so far have assignment to $X$, and how many have assignments to $Y$. Sadly, this brings the complexity up to $\Theta(T*U*N)$. Also, note that the solution generalizes to a larger number of sequences, and their values being in a larger range $\{1, \ldots, k \}$.