1.8: Partitioning

The last problem in chapter 1 is intended to warn against the follies of reckless recursion. It works well for a small problem space but quickly blows up once we increase it. The problem is to divide a treasure (e.g. consisting of items valued at $5, $2, $4, $8 and $1) into shares. 

findshare accepts a target and a list of valuables and returns a solution. If the target is 0 returns a list with zero elements and if target is less than zero or the treasure has no elements it returns a nil value. It then splits the treasure list into a first element and the tail and attempts to find a solution with that first element. If that fails, it tries again but now without the first element. Repeating this for every element in the list, we've exhausted the problem space and have found a solution if it exists at all. 

func findshare(target int, treasures []int) []int {
 if target == 0 {
  return make([]int, 0)
 }
 if target < 0 || len(treasures) == 0 {
  return nil
 }
 first, rest := treasures[0:1], treasures[1:]
 solution := findshare(target-first[0], rest)
 if solution != nil {
  return append(first, solution...)
 }
 return findshare(target, rest)
}

The main function simply creates a treasure list, calculates it total value, asks for a two way split, and prints the result.

func main() {
 treasure := []int{5, 2, 4, 8, 1}
 total := 0
 for _, v := range treasure {
  total += v
 }
 share := findshare(total/2, treasure)
 fmt.Print(share)
}

Get the source at GitHub.