aaa='123456789'
bbb='+- '
import re
result=[]
for i in range(3**8):
    temp=aaa[0]
    temp2=i
    temp3=0
    for j in range(1,9):
        temp3=temp2%3
        temp2=temp2//3
        temp+=bbb[temp3]+aaa[j]
    temp=re.sub(' ','',temp)
    exec("temp4="+temp)
    if temp4==100:
        result.append(temp)

print(result,len(result))

... 좀 날림이긴 하네요... 1부터 9까지의 수를 사이에 3가지 종류가 8번 들어가니 8자리 3진법 수 를 만들어(이것도 좀 날림이지만.. 거꾸로된 3진법수라니..) 상응하는 부호(+ OR - OR '')를 넣어 스트링 문을 만든후 exec 문을 통해 100이 나오는지 확인 하였습니다. 그리고 코드가 구질해서 죄송합니다.

eval을 쓴게 좀 아쉽군요.

digits = [*"1".."9"]
["-","+",""].repeated_permutation(8).select { |symbols|
  symbols << nil
  100 == eval([digits, symbols].transpose.flatten.join)
}.size

재귀호출로 해결할 수 있는 재밌는 문제군요! 저는 다음과 같은 아이디어를 기반으로 코드를 구현했어요: 우선 "1 2 3 4 5 6 7 8 9"라는 문자열을 고려해봅시다. 그렇다면 인덱스 1,3,5,7,9,11,13,15에 +,-,혹은 아무것도 넣지 않을수도 있습니다.따라서 총 3^8 = 6561경우만 고려하면되므로 그냥 완전탐색을 시도해볼만합니다.따라서 모든 경우를 다 시도해본뒤에 만들어진 문자열이 100을 만드는지 확인만해주면 됩니다. C++로 구현했어요.

#include <iostream> 
#include <cstdlib> 
#include <cstdio> 
#include <string> 
#include <sstream> 
#include <vector> 
#include <algorithm> 
using namespace std;  

int toInt(string s){
    int n; 
    istringstream iss (s); 
    iss >> n; 
    return n; 
}

bool chk(string _s){ //주어진 문자열이 100을 만드는지 판별. 
    string s = ""; 
    for (int i = 0; i < _s.size(); i++){
        if (_s[i]==' ') continue;  
        else s += _s[i];  
    }
    string t = ""; 
    vector<string> num; 
    for (int i = 0; i < s.size(); i++){
        if (s[i] >= '1' && s[i] <= '9'){
            t += s[i]; 
        }else if (s[i] == '+' || s[i] == '-'){
            num.push_back(t);  
            t = "";  
            num.push_back(string(1,s[i])); 
        }
    }
    num.push_back(t); 
    int res = 0;  
    int op = 2; // 0:+,1:-
    for (int i = 0; i < num.size(); i++){
        if (num[i] == "+"){
            op = 0;  
        }else if (num[i] == "-"){
            op = 1;  
        }else{
            if (op == 2) res += toInt(num[i]); 
            else if (op == 0) res += toInt(num[i]); 
            else if (op == 1) res -= toInt(num[i]); 
        }
    }
    return res == 100;  
}

vector<int> v; // +,-를 삽입가능한 포지션. 

void rec(int pos,string s){
    if (pos == 17){
        if (chk(s)){
            // 공백 매꾸기 e.g. 1 2 3+4-5+6 7-8 9 를 123+4-5+67-89로 출력하기. 
            string _s = ""; 
            for (int i = 0; i < s.size(); i++){ 
                if (s[i] == ' ') continue; 
                else _s += s[i];  
            }
            cout << _s << " = 100" << endl; 
        }
        return; 
    }
    if (find(v.begin(),v.end(),pos) != v.end()){
        char temp = s[pos]; 
        s[pos] = '+';  
        rec(pos+1,s);  
        s[pos] = '-';  
        rec(pos+1,s);  
        s[pos] = temp;  
        rec(pos+1,s);  
    }else{
        rec(pos+1,s);  
    }
}

int main(){
    for (int i = 0; i < 8; i++){
        v.push_back(2*i+1); 
    }
    rec(0,"1 2 3 4 5 6 7 8 9");  
    return 0;  
}

출력 결과는 다음과 같습니다:

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+67-89 = 100
123+45-67+8-9 = 100
123-4-5-6-7+8-9 = 100
123-45-67+89 = 100

python 2.7

import itertools

def sign_comb(l):
    sign = lambda a: a == '0' and '+' or '-'
    r = []
    for i in range(0, 2**l):
        t = str(bin(i)).replace("0b", "").zfill(l)
        r.append(map(sign, t))
    return r


def main(aList, c):
    for j in range(1, len(aList)):
        for positions in itertools.combinations(aList[:-1], j):
            positions = list(positions)
            positions.reverse()
            sign_groups = sign_comb(len(positions))
            for group in sign_groups:
                t =map(str, aList[:])
                for i, pos in enumerate(positions):
                    t.insert(pos, group[i])
                r = eval(''.join(t))
                if r == c:
                    print ''.join(t)

main([1,2,3,4,5,6,7,8,9], 100)

1,2,3,4,5,6,7,8,9 라는 숫자 사이에 부호가 들어갈 수 있는 조합을 먼저 구한 후에 또 부호가 + 또는 - 가 들어갈 수 있으므로 부호조합을 또 구하여 풀어 보았습니다.

#include <iostream>
using namespace std;

int main()
{
    int count=0;
    bool eol = 1;
    int num[9] = {1,2,3,4,5,6,7,8,9};
    unsigned char flag[8] = {0,0,0,0,0,0,0,0};
    while (eol)
    {
        for (int i = 0; i < 8; i++)
        {
            switch (flag[i])
            {
            case 0: 
                num[i+1] = num[i]*10 + num[i+1];
                num[i] = 0;
                break;
            case 1:
                num[i + 1] = num[i+1] * -1;
                break;
            case 2:
                break;
            }
        }
        if (100 == (num[0] +
            num[1] +
            num[2] +
            num[3] +
            num[4] +
            num[5] +
            num[6] +
            num[7] +
            num[8]))count++;

        for (int i = 0; i < 9; i++) num[i] = i + 1;
        flag[0]++;
        for (int i = 0; i < 8; i++)
        {
            if (flag[i] == 3)
            {
                if (i == 7) eol = 0;
                else
                {
                    flag[i+1]=flag[i+1]+1;
                    flag[i] = 0;
                }
            }
        }
    }
    cout << count;
    cin.get();
    cin.get();
    return 0;
}

이렇게 해보았습니다. 이상한가요?

Scala

def listExpr(from: Int, to: Int): List[String] = {
    def fn(n: Int, last: List[String]): List[String] = {
        def append(elements: List[String]): List[String] = {
            elements match {
                case Nil =>
                    List(
                        "" + n,
                        "-" + n
                    )
                case _ =>
                    elements.flatMap { element =>
                        List(
                            element + n,
                            element + "-" + n,
                            element + "+" + n
                        )
                    }
            }
        }

        if(n == to)
            append(last)
        else {
            fn(n + 1, append(last))
        }
    }
    fn(from, Nil)
}

val p_digit = """([+|-]?\d+)""".r
val p_add = s"$p_digit\\+(.+)".r
val p_sub = s"$p_digit\\-(.+)".r

def op(expr: String): Long = {
    expr match {
        case p_digit(number) => number.toLong
        case p_add(left, right) => op(left) + op(right) 
        case p_sub(left, right) => op(left) - op(right)
    }
}

listExpr(1, 9).filter(op(_) == 100).foreach(println)

불쌍한 C/C++ 언어 답게 "repeated_permutation"도 없고, "eval"도 없고.. 그래서 맨땅에서 다 만들었습니다. 알고리즘은 이미 나온 것과 동일합니다.

#include <iostream>
#include <cstdint>
#include <vector>
#include <cmath>

// Generate a repeated permutation for the given sequence number, length, and
// set. Example: seq = 42, length = 8, set = {a, b, c}
// (1) Convert 42 to base of 3: 1120(3)
// (2) Zero-extend to length: 00001120(3)
// (3) Map the sequence number to the elements of the set: {a, a, a, a, b, b, c, a}
std::vector<int> repeatedPermutation(uint32_t seq, size_t length,
                                     const std::vector<int> &set) {
  if (seq >= pow(set.size(), length))
    return {};

  std::vector<int> perm;
  const size_t base = set.size();
  for (size_t i = 0; i < length; ++i) {
    perm.push_back(set[seq % base]);
    seq = seq / base;
  }

  return perm;
}

int main() {
  enum opcode_t {
    opAdd = 0,
    opSub = 1,
    opConcat = 2,
    opEnd = 3,
  };

  int answer = 0;
  for (uint32_t i = 0; i < pow(3, 8); ++i) {
    auto opcodes = repeatedPermutation(i, 8, {opAdd, opSub, opConcat});

    // opConcat is denoted as "...".
    //                               *
    // opr:  0   1   2   3   4   5   6   7  
    //     1 + 2 + 3 - 4 + 5 + 6 + 7...8 + 9 = 100
    //     ~~~~~~~~~~~~~~~~~~~~~ ~ ~
    //             acc      prv_op opr
    //
    // At 6, opr is 7 and opConcat is given. Just perform "opr = opr * 10 + 8".
    //
    //                                   *
    // opr:  0   1   2   3   4   5   6   7  
    //     1 + 2 + 3 - 4 + 5 + 6 + 7...8 + 9 = 100
    //     ~~~~~~~~~~~~~~~~~~~~~ ~ ~~~~~
    //             acc      prv_op  opr
    //
    // At 7, perform "acc = prvOp(acc, opr)", "prvOp = '+'", "opr = 9".
    //       And, exceptionally (this is the last operator), consume prvOp and
    //       opr one more time.
    //
    int acc = 0, operand = 1;
    opcode_t prevOpcode = opAdd;
    for (int k = 0; k < 9; ++k) {
      opcode_t curOpcode;
      if (k < 8) {
        curOpcode = static_cast<opcode_t>(opcodes[k]);
        if (curOpcode == opConcat) {
          operand = operand * 10 + (k + 2);
          continue;
        }
      } else {
        curOpcode = opEnd; // Just bogus value; nobody will use it really.
      }

      acc = (prevOpcode == opAdd) ? (acc + operand) : (acc - operand);
      prevOpcode = curOpcode;
      operand = (k + 2);
    }

    if (acc != 100)
      continue;

    static const char *opStr[] = {" + ", " - ", ""};
    std::cout << '1';
    for (int k = 0; k < 8; ++k)
      std::cout << opStr[opcodes[k]] << k + 2;
    std::cout << " = " << acc << std::endl;
    ++answer;
  }
  std::cout << answer << std::endl;
  return 0;
}

정답은 총 11개 나오네요. Evaluation 코드에서 약간 삽질..

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

재귀로 풀어보았습니다.
python 3.4.1
result : ['1+23-4+56+7+8+9', '12+3-4+5+67+8+9', '1+2+34-5+67-8+9', '1+2+3-4+5+6+78+9', '123-4-5-6-7+8-9', '123+45-67+8-9', '1+23-4+5+6+78-9', '12-3-4+5-6+7+89', '12+3+4+5-6-7+89', '123-45-67+89', '123+4-5+67-89']

def make_3op(prev_list, number_string):
    result = []
    result.extend([item + '+' + number_string for item in prev_list])
    result.extend([item + '-' + number_string for item in prev_list])
    result.extend([item + number_string for item in prev_list])
    return(result)

def make_total_string(number):
    if (number==1):
        return(['1'])
    else :
        prev_list = make_total_string(number-1)
        return(make_3op(prev_list, str(number)))

def solution():
    total_string = make_total_string(9)
    total_result = [eval(item) for item in total_string]
    answer = [total_string[item] for item in range(len(total_string)) if total_result[item]==100]
    print(answer)

solution()

    Sub Main()
        Dim nLine As String = "123456789"
        Dim oPs As String = "+- "

        For i As Integer = 1 To 3 ^ 8
            Dim line As String = nLine(0)
            Dim tmp As Integer = i
            Dim oIdx As Integer = 0

            For j As Integer = 1 To 8
                oIdx = tmp Mod 3
                tmp = tmp / 3
                line &= oPs(oIdx).ToString.Replace(" ", "") + nLine(j)
            Next

            If eval(line) = 100 Then
                Console.WriteLine(line)
            End If
        Next

        Console.ReadLine()
    End Sub

    Public Function eval(line As String) As Integer
        Dim r As Integer = 0

        Dim ns() As Integer = Array.ConvertAll(line.Split("+"c, "-"c), Function(d As String) CInt(d))
        Dim ops() As Integer = Array.ConvertAll(line.Split("1"c, "2"c, "3"c, "4"c, "5"c, "6"c, "7"c, "8"c, "9"c, "0"c).Where(Function(d As String) d.Length > 0).ToArray,
                                               Function(d As String) CInt(IIf(d = "+", 1, -1)))

        r = ns(0)

        For i As Integer = 1 To ns.Length - 1
            r += ops(i - 1) * ns(i)
        Next

        Return r
    End Function

Lee SeungChan 님의 알고리즘을 참고했습니다.

그냥 단순하게 for문 무작정 돌렸습니다.

num = list('123456789')

#56, 67, 78, 89 의 경우에만 사칙연산을 통해 100을 만들 수 있다.
count = 0
operator = ['+','-','']

for op1 in operator:
    for op2 in operator:
        for op3  in operator:
            for op4 in operator:
                for op5 in operator:
                    for op6 in operator:
                        for op7 in operator:
                            for op8 in operator:
                                if eval(num[0] + op1 + num[1] + op2 + num[2] + op3 + num[3] +
                                        op4 + num[4] + op5 + num[5] + op6 + num[6] + op7 + num[7] +
                                        op8 + num[8]) == 100:
                                    count += 1

print('총 %d회 발생' % count)

*python으로 작성하였습니다 모든 연산자 조합을 구한뒤뒤 결과가 연산 결과가 100인 조합만 골라냈습니다.

op=['-','+',""]
result=[]
cnt=0
for i in range(pow(3,8)):
    x=i
    ops=[]
    for j in range(7):
        x,remain=divmod(x,3);ops.append(remain)
    ops.append(x)
    #print ops
    s=[j for j in range(1,10)]
    for k in range(8,0,-1):
        s.insert(k,op[ops[k-1]])

    statment="".join(str(c) for c in s)

    if(eval(statment)==100):
        cnt+=1
        result.append(statment)

print cnt,result

from itertools import product as p
n='123456789'
count=0
for pr in p((0,1,2),repeat=8):
    if eval(''.join(a+('','+','-')[b] for a,b in zip(n,pr+(0,)))) == 100:
        count +=1
print count

Ruby

프로덕트n = 프로덕트(프로덕트n-1,n) #=> 가령, 3까지의 조합은 cases[3] = cases[cases[2],3]

cases = ->a,b { [*a].product(['+','-',''],[b]).map &:join }
case_cnt = ->n { (1..9).reduce(&cases).select {|e|eval(e)==n} }

One-Liner.

(1..9).reduce {|a,e| [*a].product(['+','-',''],[e]).map &:join }.count{|e|eval(e)==100}

Test

expect(cases[1,2]).to eq %w(1+2 1-2 12)
expect(cases[cases[1,2],3]).to eq %w(1+2+3 1+2-3 1+23 1-2+3 1-2-3 1-23 12+3 12-3 123)
expect(case_cnt[100].size).to eq 11

Output

case_cnt[100].size #=> 11
case_cnt[100]
#=> ["1+2+3-4+5+6+78+9", "1+2+34-5+67-8+9", "1+23-4+5+6+78-9", "1+23-4+56+7+8+9", "12+3+4+5-6-7+89", "12+3-4+5+67+8+9", "12-3-4+5-6+7+89", "123+4-5+67-89", "123+45-67+8-9", "123-4-5-6-7+8-9", "123-45-67+89"]

파이썬3.4입니다. 재귀함수로 풀었구요. 다른분과 결과는 같은데, 저같은 경우 1도 +, -를 나눠서 계산했기 때문에 이 결과도 나왔네요....
-1+2-3+4+5+6+78+9 = 100...
12개 나왔어요~

def f(li, exp = 0, p = ''):
    '''
    li = 앞에서 1~3자리를 자르고 남은 리스트
    exp = 자른 숫자를 더하거나 뺀다
    p = 출력하기 위한 매개변수
    '''
    if not li:
        print(p, '= 100') if exp == 100 else None
        return
    if len(li) >= 1: #1자리 자른다
        f(li[1:], exp + li[0], p + '+' + str(li[0]))
        f(li[1:], exp - li[0], p + '-' + str(li[0]))
    if len(li) >= 2: #2자리 자른다
        two = int(str(li[0]) + str(li[1]))
        f(li[2:], exp + two, p + '+' + str(two))
        f(li[2:], exp - two, p + '-' + str(two))
    if len(li) >= 3: #3자리 자른다
        three = int(str(li[0]) + str(li[1]) + str(li[2]))
        f(li[3:], exp + three, p + '+' + str(three))
        f(li[3:], exp - three, p + '-' + str(three))

li = list(range(1, 10))
f(li)

C#으로 작성했습니다.

        public int ConsequenceArithmetic()
        {

            var count = 0;
            var input = "123456789";
            var operators = "+- ";

            for (int i = 0; i < Math.Pow(3, 8); i++)
            {
                var line = input.First().ToString();
                var temp = i;
                for (int j = 1; j <= 8; j++)
                {
                    var index = temp%3;
                    temp = temp/3;
                    line += operators[index].ToString().Replace(" ", "") + input[j];
                }
                count = Validation(line) == 0 ? 1 : 0;
            }

            return count;

        }

        public int Validation(string line)
        {
            var converts = Array.ConvertAll(line.Split('+', '-'), Convert.ToInt32);
            var operations =
                Array.ConvertAll(
                    line.Split('1', '2', '3', '4', '5', '6', '7', '8', '9', '0')
                        .Where(d => d.Length > 0).ToArray(),
                    d => Convert.ToInt32((d == "+" ? 1 : -1)));
            var first = converts.First();
            for (int i = 1; i <= converts.Length - 1; i++) 
                first += operations[i - 1] * converts[i];
            return first;
        }

from itertools import product
li = []
for i in product(('+','-',''), repeat = 8):
    k = '1'+''.join(i[x]+'23456789'[x] for x in range(8))
    if eval(k) == 100:li.append(k)
print(li)

파이썬 3.5.1

하스켈로 풀어보았습니다. 하스켈은 초보라 뭔가 좀 거시기하네요.

import Control.Applicative

repeatedPermutation :: [a] -> Int -> [[a]]
repeatedPermutation xs n =
    let ys = map (:[]) xs 
     in helper ys xs (n-1)   
        where
            helper :: [[a]] -> [a] -> Int -> [[a]]
            helper ys xs 0 = ys
            helper ys xs n = let zx = (:) <$> xs <*> ys in helper zx xs (n-1)

ops = repeatedPermutation ["", "+", "-"] 9
nums = map (:[]) "123456789"
equations = map (concat . concat . map (\(x, y) -> [y,x]) . zip nums) ops


parseEquation :: String -> Int
parseEquation  =
    sum . helper [] "0"
    where
        helper :: [Int] -> String -> String -> [Int]
        helper result temp [] = (read . reverse $ temp):result
        helper result temp (x:xs)
            | x == '+'  = helper ((read . reverse $ temp):result) [] xs
            | x == '-' =  helper ((read . reverse $ temp):result) [x] xs
            | otherwise = helper result (x:temp) xs


main = putStrLn . unlines $ [x| x <- equations, (head x) /= '+', parseEquation x == 100]

답은 아래와 같이 나오네요

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

재귀를 통한 모든 경우의 수를 생각하는 풀이..

#include <stdio.h>

int arr[10];
int count=0;
int cal(int index, int sum);

void main() {
    for(int i=0;i<10;i++)
        arr[i] = i;
    cal(1, 0);
    printf("%d", count);
}

int cal(int index, int sum) {
    if(index>=10) {
        if(sum == 100)
            count++;
        return sum;
    }
    int ex_sum = sum;
    sum = sum + arr[index];
    sum = cal(index+1, sum);

    sum = ex_sum;
    sum = sum - arr[index];
    if(sum > 0)
        sum = cal(index+1, sum);

    if(index < 9) {
        sum = ex_sum;
        sum = sum + (arr[index]*10 + arr[index+1]);
        sum = cal(2+index, sum);

        sum = ex_sum;
        sum = sum - (arr[index]*10 + arr[index+1]);
        if(sum > 0)
            sum = cal(2+index, sum);
    }

    if(index < 8) {
        sum = ex_sum;
        sum = sum + (arr[index]*100 + arr[index+1]*10 + arr[index+2]);
        sum = cal(3+index, sum);

        sum = ex_sum;
        sum = sum - (arr[index]*100 + arr[index+1]*10 + arr[index+2]);
        if(sum > 0)
            sum = cal(3+index, sum);
    }

    return sum;
}

import javax.script.ScriptEngine;
import javax.script.ScriptEngineManager;
import javax.script.ScriptException;
import java.util.ArrayList;
import java.util.List;

public class SerialNumber {

    public static void main(String[] args) throws ScriptException {

        int[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9};

        String[] b = {"+", "-", " "};
        List<String> c = new ArrayList<>();

        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 3; k++) {
                    for (int l = 0; l < 3; l++) {
                        for (int m = 0; m < 3; m++) {
                            for (int n = 0; n < 3; n++) {
                                for (int o = 0; o < 3; o++) {
                                    for (int p = 0; p < 3; p++) {
                                        String d = b[p] + b[o] + b[n] + b[m] + b[l] + b[k] + b[j] + b[i];
                                        c.add(d);
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

        for (int i = 0; i < 6561; i++) {
            String[] f = c.get(i).split("");
            String q = "";
            for (int j = 0; j < 8; j++) {
                q += a[j] + f[j];
            }
            q += a[8];
            String t = q.toString().replaceAll(" ", "");
            ScriptEngine engine = new ScriptEngineManager().getEngineByName("nashorn");
            if ((Integer) engine.eval(t) == 100) {
                System.out.println(t);
            }
        }
    }
}

아주...간단하게 풀었습니다.

1부터 9까지는 모두 8개의 수들 사이의 공백이 존재하고, 공백 사이에는 + 또는 -, 그리고 아무것도 안 들어갈 수도 있습니다.(위 예시에서 7과 8을 붙여 78이라고 쓴 것과 같이) 그러면 경우의 수는 3가지고, 공백이 8개니까 총 경우의 수는 3^8=6561가지 입니다. 그러면 6561가지 경우를 모두 따져 봐서 마지막에 결과가 100인지 아닌지로 분류해 몇가지 인지 출력하면 되겠네요.

def do(i = 2, exp = '1'):
    if i > 9:
        if eval(exp) == 100: print(exp, '= 100')
        return eval(exp) == 100

    else:
        return  do(i + 1, exp + str(i)) + \
                do(i + 1, exp + '+' + str(i)) + \
                do(i + 1, exp + '-' + str(i))

Haskell

eval 없이 수열을 직접 구합니다.

두 번째 숫자부터 매 숫자마다 이전 숫자와 연결되거나 분리되는 경우 두 가지로 분기되므로 총 2^8 개의 수열이 있습니다. 매 수열마다 2^n (n은 수열의 길이) 개의 가능성을 일일히 체크합니다.

import Control.Monad (foldM, mapM)
main = mapM_ (print . reverse) $ filter ((== 100) . sum) $ mapM (\x -> [x, -x]) =<< seqs
    where seqs = foldM (\(x:xs) d -> [(10 * x + d):xs, d:x:xs]) [1] $ [2..9]

출력

[123,-45,-67,89]
[123,45,-67,8,-9]
[123,4,-5,67,-89]
[123,-4,-5,-6,-7,8,-9]
[12,3,-4,5,67,8,9]
[12,-3,-4,5,-6,7,89]
[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]

3진법으로 풀었습니다. 맨앞에도 '-'가 올 수 있는것,

맨앞에 부호없음과 '+'는 같은것임을 고려해서 범위를 설정했습니다.

def convert_3(x):
    a = []
    while x:
        a.append(str(x % 3))
        x //= 3
    return ''.join(a[::-1])

results = []
for i in range(3**9, 3**9 + 2*3**8):
    t = convert_3(i).replace('2', '+').replace('1', ' ').replace('0', '-')
    s = ''
    for i in range(1, 10):
        s += t[i] + str(i)
    s = s.replace(' ', '')
    if eval(s) == 100:
        results.append(s)
for i, x in enumerate(results):
    print(i+1, x)

결과

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

Process finished with exit code 0

Swift입니다.

재귀 호출을 해서, 8단계로 +,-, 혹은 두 숫자를 합치는 조합으로 숫자 배열을 만듭니다. 숫자 배열에는 양수,음수만 들어 있게 됩니다. 합쳐지는 경우가 있기 때문에 배열의 크기는 모두 다르게 됩니다. reduce를 이용해서 배열의 합을 구해서 100인 경우, 화면에 조합을 출력하게 했습니다.

import Foundation

let operators = ["+","-","_"]
var testNumbers = [1,2,3,4,5,6,7,8,9]

func printNumbers(_ numbers: [Int]) {
    var isFirst = true
    for number in numbers {
        if isFirst {
            print("\(number) ", terminator: "")
            isFirst = false
        } else {
            print("\(number < 0 ? "-" : "+") \(number < 0 ? number * -1 : number) ", terminator: "")
        }
    }
    print(" = 100")
}

func find100(_ depth: Int, _ numbers: [Int]) {
    if depth == 0 {
        if numbers.reduce(0, {$0 + $1}) == 100 {
            printNumbers(numbers)
        }
    } else {
        let index = numbers.count - depth - 1
        for op in operators {
            var nums = numbers
            if op == "_" {  // Merge
                if nums[index] > 0 {
                    nums[index] = nums[index] * 10 + nums[index + 1]
                } else {
                    nums[index] = nums[index] * 10 - nums[index + 1]
                }
                nums.remove(at:index + 1)
            } else if op == "-" {   // Negative
                nums[index + 1] *= -1
            }

            find100(depth - 1, nums)
        }
    }
}

find100(8, testNumbers)

결과는...

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 + 67 - 89  = 100
123 + 45 - 67 + 8 - 9  = 100
123 - 4 - 5 - 6 - 7 + 8 - 9  = 100
123 - 45 - 67 + 89  = 100

a = ['+','-','']
ans = []
for i in range(3**8):
    r = ''
    for j in range(1,9): r += str(j)+a[(i//(3**(j-1)))%3]
    r += '9'
    if eval(r) == 100: ans.append(r)
print(ans, len(ans))

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

sequence_num = [str(i) for i in range(1,10)]
cal_list = ['+','-','']   
total_len = 3 ** 8


cal_before_assign = [ [] for i in range(total_len)] # 3^ 8 개의 조합이 나온다.
cal_assigned = cal_before_assign.copy() # 모든 가능한 연산 조합을 넣을 리스트

for idx in range(8):
    for i, cal in enumerate(cal_list * (3 ** idx)):
        batch_size = total_len //( 3 ** (idx + 1) )
        for j in range(batch_size * i , batch_size * (i+1)):
            cal_assigned[j].append(cal)


formula_list = [] # 숫자와 연산이 합쳐진 리스트
for cal_list in cal_assigned:
    each_formula = ''
    for num, cal in zip(sequence_num[:-1], cal_list):
        each_formula += num + cal
    each_formula += '9'
    formula_list.append(each_formula)

result100_formula = [form for form in formula_list if eval(form) == 100] # 결과가 담긴 리스트(문자열)

print(result100_formula)

library(gtools)

seq_num <- c(1:9)
set_symbol <- c('+', '-', '')
seq_symbol <- permutations(3, 8, v = set_symbol, repeats.allowed = T)

for (i in 1:nrow(seq_symbol)){
  if (seq_symbol[i, 1] == ''){
    temp <- paste(seq_num, seq_symbol[i, ], sep = '', collapse = '')
  } else if (seq_symbol[i, 1] != ''){
    temp <- paste(seq_num, seq_symbol[i, ], sep = '', collapse = '')
    temp <- substr(temp, 1, (nchar(temp) - 1))
  }
  if (eval(parse(text = temp)) == 100){
    print(temp)
  }
}

answer=100
n='123456789'
sym=' +-'
count=0

def numtosym(num):
    symstring=''
    while True:
        symstring=sym[num%len(sym)]+symstring
        num=num//len(sym)
        if len(symstring)==len(n)-1:
            break
    return symstring

for i in range(len(sym)**(len(n)-1)):
    symterm=numtosym(i)
    term=n[0]
    for j in range(len(symterm)):
        term=term+symterm[j]+n[j+1]
    term=term.replace(' ','')
    if eval(term)==answer:
        print("{} = ".format(answer)+term)
        count+=1
print("\nTotal number of ways = {}".format(count))

모든 경우의 수를 구한뒤 각 식의 값이 100이 되는 부분만 필터링했습니다.

from itertools import product

def insertNumbers(L):
    Q = L[:]
    for i in range(9, 0, -1):
        Q.insert(i-1, "%d" %i)
    return Q

combs = list(product(['', '+', '-'], repeat=8)) #모든 경우의 수
combs = list(map(list, combs))  #튜플을 리스트로 바꿔줌
combs = list(map(insertNumbers, combs))  #1부터 9까지 숫자를 삽입
combs = list(map("".join, combs))  #이어붙이기
results = list(filter(lambda x : True if eval(x)==100 else False, combs))
#식을 계산했을 때 100이 되는 부분만 찾기


print(results)

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

def ToTri(n) :
    if str(n) == '0' :
        return list(map(int, list('0'*9)))
    else :
        res, k, ret = '', 0, ''
        while n != 0 :
            if 3 ** k > n :
                res = str(k-1) + res
                n = n - (3**(k-1))
                k = 0
            else :
                k += 1
        for ke in range(0, max(map(int, list(res)))+1) :
            ret = str(res.count(str(ke))) + ret
        return list(map(int, list(ret.rjust(9, '0'))))

NUM_LIST, HUG_LIST = [str(i) for i in range(1, 10)], ['+', '-', '']

def KIG(li, hug, result) :
    sho = 0
    while sho != 6561 :
        for p in range(0, 9) :
            result += hug[ToTri(sho)[p]]+li[p]
        if eval(result) == 100 :
            print(result)
        sho += 1
        result = ''
KIG(NUM_LIST, HUG_LIST, '')

아직 실력이 많이 부족함을 느꼈습니다.

결과

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

eq=["+","-",""]  #+(더하기), -(빼기), ""(공백)
numbers=["1"," ","2"," ","3"," ","4"," ","5"," ","6"," ","7"," ","8"," ","9"] #인덱스 1,3,5,7,9,11,13,15에 eq의 요소를 넣고 재귀
i=1 #리스트 인덱스
def solve(lst):
    global i
    if i==17: #15번 인덱스까지 다 넣고 나면 i가 17이 되므로 최종적으로 return
        if eval("".join(lst))==100: #만약 모든 인덱스가 eq의 요소로 채워진 리스트의 합이 100이 되면 출력
            print("".join(lst))
        return
    else:
        for e in eq:
            lst[i]=e
            i+=2
            solve(lst)
            i-=2
            lst[i]=" "
solve(numbers)

결과

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