Sums Puzzle

I got this puzzle from my friend Andy Kelly who is also a regular contributor to SQL Server Magazine. He found it in one of the magazine’s forums. It’s not a very difficult puzzle but quite fun to work on, so I thought I’d share.

Given the set of integers \{1, 2, 3 and 4\}, get all the variations of distinct values that sums up between the range 7-9. In this case, the output should be:

3 + 4 = 7

2 + 3 + 4 = 9

1 + 3 + 4 = 8

1 + 2 + 4 = 7

Of course, try to think of a solution that would be generic enough to be used with other sets of integers and other sum ranges as well.

I’m going to present the solution that I provided to Andy, but if you want to work on a solution of your own, you might prefer not to continue reading further yet.

Here’s my solution:

with nums as

(

  select 1 as n

  union all select 2

  union all select 3

  union all select 4

),

formulas as

(

  select

    cast(n as varchar(1000)) as formula,

    n,

    n as total

  from nums

  where n <= 9

  union all

  select

    cast(formula + ' + ' + cast(cur.n as varchar(10)) as varchar(1000)),

    cur.n,

    prv.total + cur.n

  from formulas as prv

    join nums as cur

      on cur.n > prv.n

  where prv.total + cur.n <= 9

)

select formula + ' = ' + cast(total as varchar(10)) as formula

from formulas

where total between 7 and 9;

The code first defines a CTE called nums representing the set of input numbers. This one can be adjusted to include other input numbers, of course. The code defines a second CTE called formulas. This CTE is recursive. The anchor member of the CTE formulas filters only the numbers that are smaller than or equal to the upper boundary of the requested sum range. In the SELECT list, the anchor member starts building the result formula—for now including only the current number, and also returns the number as the last number used (n), and as the sum so far (total).

The recursive member of the CTE formula joins the previous result set with Nums, matching to each row from the previous result set all numbers that are greater than the last one used. The recursive member filters only those cases where the last total plus current number is smaller than the upper boundary value of the sum range. In the SELECT list, the recursive member concatenates the current number to the formula constructed so far, returns the current number as the last number used, and adds the current number to the previous total to produce the current total.

Finally, the outer query filters only the cases where the total is in the right range, and concatenates the result of the sum to the formula.

Cheers,

BG