This one is a little different because it is a problem I myself came up with. Asking AI about it, it seems like what I describe here is similar to problems in leetcode and elsewhere known as “k-sum”, though I think this formulation is a bit different. I’m not even sure that this doesn’t have a much easier solution, but running through it, it’s not obvious

Problem Statement

Given a range of numbers \( [1,N] \) and a sum S, what are all sets of K numbers from the range (without replacement) that add up to S?

Example:

Of the range [1,3], \( K=2 \) and \( S=4 \) you have only the single-element set {(1 3)}
Of the range [1,4], \( K=2 \) and \( S=5 \) you have the set {(1 4) (2 3)}
Of the range [1,5], \( K=3 \) and \( S=7 \) you have again a single-element set {(1 2 4)}. No other combinations of three numbers from this range work.
Of the range [1,7], \( K=3 \) and \( S=10 \) you have the set {(1 2 7) (1 3 6) (1 4 5) (2 3 5)}

Brainstorming

Lets just chart out a bunch of examples and see what patterns we see. How do you pick subsets from a range anyways?

Of the range [1,5], \( K=3 \)

1	2	3
1	2	4
1	2	5
1	3	4
1	3	5
1	4	5
2	3	4
2	3	5
2	4	5
3	4	5

I think that’s all the combinations? So the trick was basically to increase the rightmost column starting with one more than the number to the left. Once you hit five, you increment the number to the left and start again

Now do that and layer over the sum thing which determines what the third number should be

Of the range [1,7], \( K=3 \) and \( S=10 \)

1	2	7
1	3	6
1	4	5
1	5	-
1	6	-
1	7	-
2	3	5
2	4
2	5	-
3	4
3	5	-
3	6	-
4	5	-
5	6
6	7

Lets do one more

Of the range [1,9], \( K=3 \) and \( S=15 \)

In the table below, a blank in the third column indicates that the options for the current run have been exhausted, whereas a dash that the only way to resolve it is with a duplicate

1	2	12
1	3	11
1	4	10
1	5	9
1	6	8
1	7
2	3	10
2	4	9
2	5	8
2	6	7
2	7
3	4	8
3	5	7
3	6
4	5	6
4	6
5	6	-
5	7	-
5	8	-
5	9	-
6	7	-
6	8	-

If you cannot place a digit because it would equal or exceed with the prevopis (eg (1 7 7) or (2 7 6)) then no point decrementing further as it would have already been covered higehr up on the list
What if \( S=14 \)?

1	2	11
1	3	10
1	4	9
1	5	8
1	6	7
1	7
2	3	9
2	4	8
2	5	7
2	6
3	4	7
3	5	6
3	6
4	5
5	6	-
5	7	-
5	8	-
6	7	-

oh that does look like a sort of pattern, we lost a set from the second and fourth groupings. If \( S=13 \) I can see that first grouping would lose 1 more set

Lets try that again but with \( S=15, K=4 \)

1	2	3	9
1	2	4	8
1	2	5	7
1	2	6
1	3	4	7
1	3	5	6
1	3	6
2	3	4	6
2	3	5
2	4	5
2	5	6
3	4	5

Ah, so look, once we can no longer have the numbers be increasing, we should go on to the next line

There is something recursive here. For example if I have \( S=15, K=4 \)

The question marks are the same as \( S=14, K=3 \) when start_at=2

Which is the same as \( S=12,K=2 \) when start_at=3

Which is the same as \( S=9,K=1 \) and start_at doesn’t matter

Lets see if I can actually implement this

Python Implementation

:header-args+: :exports both

def get_lowest_incrementing_addends(lowest_first_number: int, k: int, desired_sum: int):
    assert 1<=k
    assert 0<desired_sum

    if desired_sum < lowest_first_number:
        return

    if k==1:
        yield desired_sum
        return

    yield lowest_first_number

    yield from get_lowest_incrementing_addends(lowest_first_number+1, k-1, desired_sum-lowest_first_number)

Lets test that

print(list(get_lowest_incrementing_addends(1, 4, 15)))
print(list(get_lowest_incrementing_addends(2, 4, 15)))
print(list(get_lowest_incrementing_addends(2, 3, 15)))

ok so I think that getting “all” should be similar, you just iterate upwards and spread out

from typing import Iterator

type SetOfAddends = tuple[int]

def get_incrementing_addends(lowest_first_number: int, upper_bound: int, k: int, desired_sum: int) -> Iterator[SetOfAddends]:
    assert 1<=k, "K must be positive"

    if desired_sum <= 0:
        return

    if  upper_bound <= lowest_first_number:
        return

    if desired_sum < lowest_first_number:
        return

    if k==1:
        yield (desired_sum, )
        return

    for new_lowest_first_number in range(lowest_first_number, upper_bound):
        for addends in get_incrementing_addends(new_lowest_first_number+1, upper_bound, k-1, desired_sum-new_lowest_first_number):
            yield (new_lowest_first_number,)+ addends

print(list(get_incrementing_addends(1, 9, 3, 15)))
print(list(get_incrementing_addends(1, 9, 4, 15)))

Oh snap, I think that worked!

I do suspect that some further optimization is possible, it certainly is not necessary for that final loop to run all the way up to upper_bound, but those branches would teriminate rapidly either way so I’m not concerned

Emacs Lisp Implementation

:header-args+: :exports both

I know no one cares about my abilities to code in lisp, but I do enjoy it even if the emacs flavor is not my favorite, lets just do one of those really quick. Plus, its good experience using cl-loop which I like a lot

(require 'generator)

(iter-defun gim/get-incrementing-addends (lowest-first-number upper-bound k desired-sum)
  (cl-assert (when (<= 1 k) 't) nil "k must be positive")
  (when (and (< 0 desired-sum)
             (< lowest-first-number upper-bound)
             (<= lowest-first-number desired-sum))
    (if (= k 1)
        (iter-yield (list desired-sum))
      (cl-loop for new-lowest from lowest-first-number to upper-bound
               do (cl-loop for addends iter-by (gim/get-incrementing-addends (+ 1 new-lowest) upper-bound (- k 1) (- desired-sum new-lowest))
                           do (iter-yield (cons new-lowest addends)))))))

(cl-loop for addends iter-by (gim/get-incrementing-addends 1 9 3 15)
         collect addends)

Nice! I really like lisps…

Go Implementation

:header-args+: :exports both

I’ve been poking at Go lately and while it doesn’t have generators it has channels which are a similar use case

package main

import "fmt"

func getIncrementingAddends(lowestFirstNumber, upperBound, k, desiredSum int) <-chan []int {
	resultChan := make(chan []int)

	go func() {
		defer close(resultChan)

		if k <= 0 {
			panic("K must be positive")
		}

		if desiredSum <= 0 || upperBound <= lowestFirstNumber || desiredSum < lowestFirstNumber {
			return
		}

		if k == 1 {
			if desiredSum <= upperBound {
				resultChan <- []int{desiredSum}
			}
			return
		}

		for newLowestFirstNumber := lowestFirstNumber; newLowestFirstNumber < upperBound; newLowestFirstNumber++ {
			resultsToTheRightChan := getIncrementingAddends(newLowestFirstNumber+1, upperBound, k-1, desiredSum-newLowestFirstNumber,)

			for subResult := range resultsToTheRightChan {
				result := append([]int{newLowestFirstNumber}, subResult...)
				resultChan <- result
			}
		}
	}()

	return resultChan
}

func main() {
	for addends := range getIncrementingAddends(1, 9, 3, 15) {
		fmt.Println(addends)
	}
}

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Problem Statement

Example:

Brainstorming

Python Implementation

Emacs Lisp Implementation

Go Implementation

1	2	12
1	3	11
1	4	10
1	5	9
1	6	8
1	7
2	3	10
2	4	9
2	5	8
2	6	7
2	7
3	4	8
3	5	7
3	6
4	5	6
4	6
5	6	-
5	7	-
5	8	-
5	9	-
6	7	-
6	8	-

1	2	12
1	3	11
1	4	10
1	5	9
1	6	8
1	7
2	3	10
2	4	9
2	5	8
2	6	7
2	7
3	4	8
3	5	7
3	6
4	5	6
4	6
5	6	-
5	7	-
5	8	-
5	9	-
6	7	-
6	8	-

FilesExpand file tree

README.org

Latest commit

History

README.org

File metadata and controls

Problem Statement

Example:

Brainstorming

Python Implementation

Emacs Lisp Implementation

Go Implementation

1	2	12
1	3	11
1	4	10
1	5	9
1	6	8
1	7
2	3	10
2	4	9
2	5	8
2	6	7
2	7
3	4	8
3	5	7
3	6
4	5	6
4	6
5	6	-
5	7	-
5	8	-
5	9	-
6	7	-
6	8	-