Solution: Backtracking

Solution to the problem related to backtracking.

We'll cover the following...

Let's practice what we have learned so far.

Task

An addition chain for an integer nn is an increasing sequence of integers that starts with 11 and ends with nn, such that each entry after the first is the sum of two earlier entries. More formally, the integer sequence x0<x1<x2<<xlx_0 < x_1 < x_2 < ··· < x_l is an addition chain for n if and only if

  • x0=1x_0 = 1,
  • xl=nx_l = n
...