algorithm - Unique values of expressions using given number of 2's -

given number of 2's how many unique values can formed building expressions out of @ given number of 2's involving addition or multiplication.

for example, if n = 2, can form 2 different values:

2 + 2 = 4 2 * 2 = 4 2     = 2 

for n = 3, can form 4 different values (2, 4, 6 , 8):

2 * 2 * 2 = 8 2 * 2 + 2 = 6 2 + 2 * 2 = 6 2 + 2 + 2 = 6 2 * 2     = 4 2 + 2     = 4 2         = 2 

i want know n, number of different possible values.

i tried possible combinations , adding them hash map, n increases comibnations increase exponentially brute force won't work. need way of calculating or generalized mathematical formula.

can solved using dynamic programming, because see many sub problems used repeatedly.

the other answers far assume want count number of distinct expressions. answer assumes looking number of different values these expressions can evaluate to.

let's have expression of size @ n. can rewrite 2^e[1] + 2^e[2] + ... + 2^e[m] e[i] >= 1 , e[1] + e[2] + ... + e[m] <= n.

let's assume e[1] <= e[2] <= ... <= e[m]. if e[i] = e[i+1] i, can replace 2 equal exponents single exponent e[i] + 1, since 2^e[i] + 2^e[i+1] = 2 * 2^e[i] = 2^{e[i] + 1}. since e[i] + 1 <= e[i] + e[i+1], new sequence results in same value, , still fulfills condition sum of exponents smaller or equal n.

so need count number of different sequences of exponents 0 < e[1] < e[2] < ... < e[m]. clear every 1 of represents different value, because binary representation of number unique (and distinct exponents represent binary representation).

we can use dynamic programming count these sequences, example picking exponents highest lowest.

let's define f(n,hi) number of different ways choose distinct exponents sum no more n , highest exponent <= hi. @ every step, can either choose next highest exponent arbitrarily between 1 , min(hi, n) or stop choosing exponents. have recurrence

f(0, hi) = 1  hi >= 0 f(n, hi) = 1 + sum(e = 1 min(hi, n), f(n - e, e - 1)) 

which leads simple dynamic program solve problem. answer f(n,n) - 1. need subtract one, because counted possiblity not choose exponents, results in sum 0. not allowed problem statement.

here few results:

f(1,1) - 1 = 1 f(2,2) - 1 = 2 f(3,3) - 1 = 4 f(4,4) - 1 = 6 f(5,5) - 1 = 9 f(6,6) - 1 = 13 f(7,7) - 1 = 18 f(8,8) - 1 = 24 f(9,9) - 1 = 32 f(10,10) - 1 = 42 f(11,11) - 1 = 54 f(12,12) - 1 = 69 f(13,13) - 1 = 87 f(14,14) - 1 = 109