Ways to add to $N$ using positive integers $\le N$ Given a number $N$ I want to find the number of ways to add up to it using integers in the range [1, N].
I do not want to count the same thing more than once, but I do want different orders.
For example, for $N=4$:
$1+1+2$ is a solution. So it $1+2+1$. But $1+1+2$ should not be counted twice, that is swapping the 2 1's is not a unique solution.
The full solution set for $N=4$ should be:
$1+1+1+1$
$2+1+1$
$1+2+1$
$1+1+2$
$2+2$
$3+1$
$1+3$
$4$
so I want $8$ for $N=4$
 A: There are $$2^{N-1}$$ ways to form a composition of the number $N$.  In your example, $N=4$ and the total number of compositions is $2^{4-1} = 8$ as you observed.
To see why this is the right answer, imagine you have $N$ coins lined up on the table.  You are going to insert dividers between some of the coins to separate the coins into groups.    So for example with $N=7$ we might have
$$\bullet \mid \bullet \bullet \bullet \mid \bullet \mid\bullet \bullet $$
Here we've composed $7 = 1+3+1+2$.  The compositions of $7$ as a sum of positive integers are in one-to-one correspondence with the possible positions of the dividers: for each sum, there is exactly one corresponding set of dividers.  There are $N-1$ positions for the dividers, and each position might have a divider or lack a divider, so there are $2^{N-1}$ possible ways to insert the dividers, and so $2^{N-1}$ compositions.
(Had you simply tabulated the number of compositions of $N$ for $N=1, 2, 3, 4$ you might have noticed  this yourself.)
To enumerate the possibilities, enumerate the possible sets of positions for the dividers, which are simply the base-2 numerals from $0$ through $2^{N-1}-1$, and for each one calculate the corresponding  composition. Here is example code.
A: I would go for a recursive solution. Let $A(n)$ represent the number of ways to represent $n$ in the form you suggest and now consider $A(n+1)$. Let the first contribution in our sum be $i$ where $1 \leq i \leq n+1$, then the sum of the remaining terms is $n+1-i$ and so there are precisely $A(n+1-i)$ ways to represent the remaining terms.  
