Search⌘ K
Home
Courses
Mastering Algorithms for Problem Solving in Java

Solution: Backtracking

Explore how to use recursive backtracking to compute the minimum addition chain for a positive integer. This lesson guides you through building the algorithm logic and implementing it in Java to deepen your understanding of complex problem solving with 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 1 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 nn if and only if

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