---
id: 5a23c84252665b21eecc8043
title: Сума до 100
challengeType: 1
forumTopicId: 302335
dashedName: sum-to-100
---

# --description--

Знайдіть рішення головоломки *сума до ста*.

Додайте (вставте) математичні оператори **+** чи **─** (плюс або мінус) перед будь-якою цифрою в десятковому числовому рядку **123456789** так, щоб отриманий математичний вираз у підсумку дорівнював певній сумі (у цьому знаковому випадку — **100**).

До прикладу:

<pre><b>123 + 4 - 5 + 67 - 89   =   100</b></pre>

# --instructions--

Напишіть функцію, яка враховує число як параметр. Ця функція має повернути масив, що вміщуватиме всі рішення для даного числа. Рішення має бути рядками у вигляді виразів. Наприклад: "1+23-456+78-9". Відсортуйте масив до того, як повернете його.

# --hints--

`sumTo100` має бути функцією.

```js
assert(typeof sumTo100 == 'function');
```

`sumTo100(199)` має повернути масив.

```js
assert(Array.isArray(sumTo100(199)));
```

`sumTo100(199)` має повернути `["-1+2-3+45+67+89", "123-4+5+6+78-9", "123-4+56+7+8+9"]`.

```js
assert.deepEqual(sumTo100(199), [
  '-1+2-3+45+67+89',
  '123-4+5+6+78-9',
  '123-4+56+7+8+9'
]);
```

`sumTo100(209)` має повернути `["1+234+56+7-89"]`.

```js
assert.deepEqual(sumTo100(209), ['1+234+56+7-89']);
```

`sumTo100(243)` має повернути `["-1-234+567-89", "-12+345+6-7-89", "123+45+6+78-9"]`.

```js
assert.deepEqual(sumTo100(243), [
  '-1-234+567-89',
  '-12+345+6-7-89',
  '123+45+6+78-9'
]);
```

`sumTo100(197)` має повернути `["1-2-3+45+67+89", "12+34-5+67+89", "123+4-5+6+78-9"]`.

```js
assert.deepEqual(sumTo100(197), [
  '1-2-3+45+67+89',
  '12+34-5+67+89',
  '123+4-5+6+78-9'
]);
```

# --seed--

## --seed-contents--

```js
function sumTo100(n) {

}
```

# --solutions--

```js
function sumTo100(n) {
  var permutationsWithRepetition = function(n, as) {
    return as.length > 0
      ? foldl1(curry(cartesianProduct)(as), replicate(n, as))
      : [];
  };

  var cartesianProduct = function(xs, ys) {
    return [].concat.apply(
      [],
      xs.map(function(x) {
        return [].concat.apply(
          [],
          ys.map(function(y) {
            return [[x].concat(y)];
          })
        );
      })
    );
  };

  var curry = function(f) {
    return function(a) {
      return function(b) {
        return f(a, b);
      };
    };
  };

  var flip = function(f) {
    return function(a, b) {
      return f.apply(null, [b, a]);
    };
  };

  var foldl1 = function(f, xs) {
    return xs.length > 0 ? xs.slice(1).reduce(f, xs[0]) : [];
  };

  var replicate = function(n, a) {
    var v = [a],
      o = [];
    if (n < 1) return o;
    while (n > 1) {
      if (n & 1) o = o.concat(v);
      n >>= 1;
      v = v.concat(v);
    }
    return o.concat(v);
  };

  var asSum = function(xs) {
    var dct = xs.reduceRight(
      function(a, sign, i) {
        var d = i + 1; //  zero-based index to [1-9] positions
        if (sign !== 0) {
          // Sum increased, digits cleared
          return {
            digits: [],
            n: a.n + sign * parseInt([d].concat(a.digits).join(''), 10)
          };
        } else
          return {
            // Digits extended, sum unchanged
            digits: [d].concat(a.digits),
            n: a.n
          };
      },
      {
        digits: [],
        n: 0
      }
    );
    return (
      dct.n + (dct.digits.length > 0 ? parseInt(dct.digits.join(''), 10) : 0)
    );
  };

  var asString = function(xs) {
    var ns = xs.reduce(function(a, sign, i) {
      var d = (i + 1).toString();
      return sign === 0 ? a + d : a + (sign > 0 ? '+' : '-') + d;
    }, '');

    return ns[0] === '+' ? tail(ns) : ns;
  };

  var universe = permutationsWithRepetition(9, [0, 1, -1])
    .filter(function(x) {
      return x[0] !== 1 && asSum(x) === n;
    })
    .map(asString);
  return universe.sort();
}
```
