An addition chain for an integer n is an increasing sequence of integers that starts with 1 and ends with n, such that each entry after the first is the sum of two earlier entries. More formally, the integer sequence x0 < x1 < x2 < < x` is an addition chain for n if and only if x0 = 1, x` = n, and for every index k > 0, there are indices i j < k such that xk = xi + x j . The `ength of an addition chain is the number of elements minus 1; we dont bother to count the first entry. For example, 1, 2, 3, 5, 10, 20, 23, 46, 92, 184, 187, 374 is an addition chain for 374 of length 11.

Describe a recursive backtracking algorithm to compute a minimumlength addition chain for a given positive integer n. Dont analyze or optimize your algorithms running time, except to satisfy your own curiosity. A correct algorithm whose running time is exponential in n is sufficient for full credit. [Hint: This problem is a lot more like n Queens than text segmentation.]

Please provide pseudocode along with explanation. Please do not write queens algorithm here as it is.