Add new comment

All expressions of 123456789 and signs +/- which value is 100

Submitted by st on

Suppose a string of ordered cyphers 123456789. You can insert signs "+" and "-" between any cyphers to make a correct arithmetical expression. The problem is to find all expressions which sum is 100.

This problem may be interesting for dynamic script languages having the function of a string expression evaluation.

E.g. solving in bash

$ for i in {,-}1{,+,-}2{,+,-}3{,+,-}4{,+,-}5{,+,-}6{,+,-}7{,+,-}8{,+,-}9; do (($i == 100)) && echo $i; done

Result

123+45-67+8-9
123+4-5+67-89
123-45-67+89
123-4-5-6-7+8-9
12+3+4+5-6-7+89
12+3-4+5+67+8+9
12-3-4+5-6+7+89
1+23-4+56+7+8+9
1+23-4+5+6+78-9
1+2+34-5+67-8+9
1+2+3-4+5+6+78+9
-1+2-3+4+5+6+78+9

The standard SQL has no evaluation functions. However, the recursive query approach can help.

Solution in ANSI SQL

WITH signs AS (
  SELECT '' AS s, 0 AS sv
  UNION 
  SELECT '+' AS s, 1 AS sv 
  UNION 
  SELECT '-' AS s, -1 AS sv 
),
curr (sv, c, expr, num, val) AS (
  SELECT 0 AS sv, 0 AS c, CAST('' AS varchar(20)) AS expr, 0 AS num, 0 AS val
  UNION ALL
  SELECT signs.sv AS sv, c + 1 AS c, 
         CAST(expr + signs.s + CAST((c + 1) AS varchar(1)) AS varchar(20)) AS expr,
         CASE
           WHEN signs.sv = 0 THEN num * 10 + (CASE WHEN num < 0 THEN -(c + 1) ELSE c + 1 END)
           ELSE signs.sv * (c + 1)
         END AS num,
         CASE WHEN signs.sv = 0 THEN val ELSE val + num END AS val
  FROM curr CROSS JOIN signs
  WHERE curr.c < 9 AND NOT (c = 0 AND signs.sv = 1)
)
SELECT expr, val + num AS total
FROM curr 
WHERE c = 9 AND val + num = 100

Result

expr                 total
-------------------- -----------
-1+2-3+4+5+6+78+9    100
1+2+3-4+5+6+78+9     100
1+2+34-5+67-8+9      100
1+23-4+5+6+78-9      100
1+23-4+56+7+8+9      100
12-3-4+5-6+7+89      100
12+3-4+5+67+8+9      100
12+3+4+5-6-7+89      100
123-4-5-6-7+8-9      100
123-45-67+89         100
123+4-5+67-89        100
123+45-67+8-9        100
 
(12 rows affected)