https://forum.lowyat.net/topic/3852732

pick8.go

// https://forum.lowyat.net/topic/3852732

// Quick and Dirty hack
// angch's go kata

// Original idea was to scale up and use Go channels, but we can't do
// priority queue that way.

package main

import (
	"container/heap"
	"fmt"
	"sort"
)

// Current picks, and their sum so far
type Picks struct {
	priority float32 // The priority of the item in the queue.
	index    int     // The index of the item in the heap.

	idx []int   // Not to be confused with idx, which is a set of the items we picked
	sum float32 // sum so far
}

// A PriorityQueue implements heap.Interface and holds Items.
type PriorityQueue []*Picks

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
	// We want Pop to give us the highest, not lowest, priority so we use greater than here.
	return pq[i].priority > pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}

func (pq *PriorityQueue) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Picks)
	item.index = n
	*pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	item.index = -1 // for safety
	*pq = old[0 : n-1]
	return item
}

func initTestItems() []float32 {
	items := make([]float32, 0, 0)

	items = append(items, 1.0)
	items = append(items, 2.0)
	items = append(items, 3.0)
	items = append(items, 4.0)
	items = append(items, 2.2)
	items = append(items, 0.5)
	items = append(items, 0.5)
	return items
}

func initItems() []float32 {
	i := []float64{20, 100, 500, 100, 100, 1900, 100.13, 200, 200, 300, 140, 100, 2700, 967.93, 100, 100, 4000, 100, 100, 100, 1000, 100, 200, 300, 100, 200, 100, 3000, 508.47, 20, 100, 100, 100, 100, 2445, 462.96, 195, 1000, 300, 100, 100, 20, 595.17, 250, 10, 10, 3000, 668, 113.29, 1374.68, 204.39, 697.98, 1572.19, 253, 500, 700, 500, 1100, 142.37, 2000, 475, 1850, 495, 2700, 2260.78, 500, 1270, 362.82, 1951, 444.03, 1460, 2700, 425, 2208.98, 2700, 500, 1950, 1400, 500, 2060, 2270, 1837, 2053, 751.63, 1000, 450, 1800, 1962.93, 465, 250, 2045, 300, 480, 462.87, 2470, 1514, 518.17, 3000, 2190.93, 2600, 500, 500, 500, 1004.24, 1625, 500, 2400, 2450, 780}
	sort.Sort(sort.Float64Slice(i))
	items := make([]float32, len(i))
	for k, v := range i {
		items[k] = float32(v)
	}
	return items
}

func search(items []float32, target float32, targetNumber int) {
	checks := 0

	// Create a priority queue, put the items in it, and
	// establish the priority queue (heap) invariants.
	pq := make(PriorityQueue, len(items))
	i := 0
	for idx, number := range items {
		priority := float32(0)
		if target > number {
			priority = number - target // yes, it's negative
		}
		pq[i] = &Picks{
			priority: priority,
			index:    idx,
			idx:      []int{idx},
			sum:      number,
		}
		i++
		checks++
	}
	heap.Init(&pq)

	for pq.Len() > 0 {
		picks := heap.Pop(&pq).(*Picks)

		if picks.sum == target &&
			len(picks.idx) == targetNumber {
			fmt.Println("Found it in", checks, "tries")
			for _, v := range picks.idx {
				fmt.Println(items[v])
			}
			return
		}

		lastIdx := picks.idx[len(picks.idx)-1]
		if len(picks.idx) >= targetNumber {
			continue
		}

		for lastIdx++; lastIdx < len(items); lastIdx++ {
			number := items[lastIdx]
			priority := float32(0)
			if target > number {
				priority = number - target // yes, it's negative
			}
			if target < number {
				continue
			}

			indices := make([]int, len(picks.idx)+1)
			copy(indices, picks.idx)
			indices[len(picks.idx)] = lastIdx

			newPick := &Picks{
				priority: priority,
				idx:      indices,
				sum:      picks.sum + number,
			}
			heap.Push(&pq, newPick)
			checks++
		}
	}
	fmt.Println("Give up after", checks, "tries")
}

func main() {
	//items := initTestItems()
	items := initItems()
	//search(items, 5.0, 3)
	search(items, 15629.14, 8)
}