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

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)

Mechanics of software Programming is thinking, not typing
Home \| Categories \| Tags \| Search	\| eng \| рус