Код-гольф - Реализация алгоритма выборки комбинаций

Question

Приём ответов завершён, всем спасибо за участие!
Можете оставлять свои решения, но победители уже выбраны и пересчёта не будет.

---

Приветствую.

Задача: Напишите функцию, которая из произвольного входящего массива выберет все комбинации чисел, сумма которых будет равняться 10.

Подробнее:
Диапазон чисел: 0 - 1000 включительно.
Количество чисел во входящем массиве: 1 - 10 включительно.
Уже выбранные числа могут использоваться неоднократно, но комбинации должны быть уникальны.
--- Смена позиций не делает комбинацию уникальной, т. е. [1,9] и [9,1] не позволяются).
--- При входных данных [5,5,2,3] можно сделать [5,5], [5,2,3].
Продолжительность конкурса: 14 дней.
Обязательный формат метки ответа (для автоматического парсера в таблицу):
<h2>Язык, КоличествоСимволов</h2>

Определение победителя: Определяется по градации:

1. Реализация, состоящая из наименьшего количества символов.
2. Реализация, получившая больше всего плюсов (общий рейтинг минус голоса против).
3. Реализация, время первой редакции которой раньше.

Необходимо так же давать ссылку на один из онлайн-компиляторов с Вашим рабочим кодом.
Тесты приветствуются.
Настоятельно рекомендуется давать как конкурсную версию кода (минифицированную и/или с колдунствами), так и наглядное описание этого же кода. Всем интересно не только увидеть языковую магию, но и что-то почерпнуть для себя.

От одного участника допустимо несколько ответов, если они реализованы на разных языках. Но не более одного на язык

---

Все вопросы по деталям и/или разногласиям и/или трактовке условий, прошу обсуждать в комментариях к этому сообщению или в комнате чата по код-гольфу.

---

Итоги:

Стандартные 3 места + 1 за самое большое количество плюсов (общий рейтинг минус голоса против).

1 место: @PavelMayorov - Haskell, 42 символа.
2 место: @ArtemKonovalov - Scala, 69 символов.
3 место: @Mike - Perl, 78 символов.

Зрительские симпатии: @D-side (Ruby, 84) - 19 баллов.

Поздравления всем участникам, вы хорошо сражались.
Особенно страсти накалились в самом конце, когда неожиданно было опубликовано решение обгоняющее лидера на 1 символ.
Но судьба вернула всё обратно.

Хотелось бы отметить необычное для данного соревнования решение от пользователя @AlexanderGavrikov - 1437 символов!
Это своеобразный рекорд, стоит отметить.

---

Таблица лидеров:

execute(581668);

.cssload-container,.cssload-cube{width:97px;height:97px;transform-style:preserve-3d}.cssload-container,.cssload-cube,.cssload-half1,.cssload-half2{transform-style:preserve-3d}.cssload-container{position:relative;margin:23px 84px;perspective:292px}.cssload-cube{animation:cube 11.5s forwards infinite;transform-origin:center 49px}.cssload-half1,.cssload-s1{top:0;transform-origin:50% 100%}.cssload-half1{height:39px;position:absolute;animation:half-fold 11.5s forwards infinite}.cssload-side{width:19px;height:19px;background:#ddd;position:absolute}.cssload-s1{left:39px;animation:s1ani 11.5s forwards infinite}.cssload-s2,.cssload-s3,.cssload-s4{left:39px;transform-origin:50% 0}.cssload-s2{top:19px;animation:s2ani 11.5s forwards infinite}.cssload-s3{top:39px;animation:s3ani 11.5s forwards infinite}.cssload-s4{top:58px;animation:s4ani 11.5s forwards infinite}.cssload-s5{left:19px;top:19px;transform-origin:100% 50%;animation:s5ani 11.5s forwards infinite}.cssload-s6{left:58px;top:39px;transform-origin:0 50%;animation:s6ani 11.5s forwards infinite}@keyframes cube{0%,30%{transform:rotateX(0)}40%{transform:rotateX(45deg) rotateY(0) rotate(45deg)}60%{transform:rotateX(60deg) rotateY(0) rotate(45deg)}65%,70%{transform:rotateX(60deg) rotate(45deg) rotate(180deg)}75%,80%{transform:rotateX(60deg) rotate(45deg) rotate(1turn)}90%{transform:rotateX(0) rotate(0) rotate(0)}}@keyframes s1ani{0%{opacity:1;transform:translateY(0);background:#ddd}40%{transform:rotateX(0);background:#ddd}50%{transform:rotateX(-90deg);background:#ddd}90%{transform:rotateX(-90deg)}}@keyframes s2ani{0%{opacity:0;transform:rotateX(-179deg)}10%{opacity:1;transform:rotateX(0)}40%{background:#ddd}45%,80%{background:#b4b4b4}65%{opacity:1;background:#b4b4b4}90%{opacity:1}to{opacity:0}}@keyframes s3ani{0%,10%{opacity:0;transform:rotateX(-179deg)}20%,90%{opacity:1;transform:rotateX(0)}40%{background:#ddd}45%{background:#969696}to{opacity:0}}@keyframes s4ani{0%,20%{opacity:0;transform:rotateX(-179deg)}10%,to{opacity:0}30%{opacity:1;transform:rotateX(0)}40%{transform:rotateX(0);background:#ddd}50%{transform:rotateX(90deg);background:#b4b4b4}80%{background:#b4b4b4}90%{opacity:1;transform:rotateX(90deg)}}@keyframes s5ani{0%,10%{opacity:0;transform:rotateY(-179deg)}20%{opacity:1;background:#ddd;transform:rotateY(0)}40%{transform:rotateY(0)}50%{transform:rotateY(90deg)}55%{background:#ddd}60%{background:#c8c8c8}90%{transform:rotateY(90deg);opacity:1}to{opacity:0}}@keyframes s6ani{0%,20%{opacity:0;transform:rotateY(179deg)}30%{opacity:1;transform:rotateY(0)}40%{transform:rotateY(0)}50%{transform:rotateY(-90deg);background:#ddd}60%,80%{background:#c8c8c8}90%{opacity:1;transform:rotateY(-90deg)}to{opacity:0}}@keyframes half-fold{0%,50%{transform:rotateX(0)}60%,90%{transform:rotateX(-90deg)}}
.cssload-container,.cssload-cube{width:97px;height:97px;transform-style:preserve-3d}.cssload-container,.cssload-cube,.cssload-half1,.cssload-half2{transform-style:preserve-3d}.cssload-container{position:relative;margin:23px 84px;perspective:292px}.cssload-cube{animation:cube 11.5s forwards infinite;transform-origin:center 49px}.cssload-half1,.cssload-s1{top:0;transform-origin:50% 100%}.cssload-half1{height:39px;position:absolute;animation:half-fold 11.5s forwards infinite}.cssload-side{width:19px;height:19px;background:#ddd;position:absolute}.cssload-s1{left:39px;animation:s1ani 11.5s forwards infinite}.cssload-s2,.cssload-s3,.cssload-s4{left:39px;transform-origin:50% 0}.cssload-s2{top:19px;animation:s2ani 11.5s forwards infinite}.cssload-s3{top:39px;animation:s3ani 11.5s forwards infinite}.cssload-s4{top:58px;animation:s4ani 11.5s forwards infinite}.cssload-s5{left:19px;top:19px;transform-origin:100% 50%;animation:s5ani 11.5s forwards infinite}.cssload-s6{left:58px;top:39px;transform-origin:0 50%;animation:s6ani 11.5s forwards infinite}@keyframes cube{0%,30%{transform:rotateX(0)}40%{transform:rotateX(45deg) rotateY(0) rotate(45deg)}60%{transform:rotateX(60deg) rotateY(0) rotate(45deg)}65%,70%{transform:rotateX(60deg) rotate(45deg) rotate(180deg)}75%,80%{transform:rotateX(60deg) rotate(45deg) rotate(1turn)}90%{transform:rotateX(0) rotate(0) rotate(0)}}@keyframes s1ani{0%{opacity:1;transform:translateY(0);background:#ddd}40%{transform:rotateX(0);background:#ddd}50%{transform:rotateX(-90deg);background:#ddd}90%{transform:rotateX(-90deg)}}@keyframes s2ani{0%{opacity:0;transform:rotateX(-179deg)}10%{opacity:1;transform:rotateX(0)}40%{background:#ddd}45%,80%{background:#b4b4b4}65%{opacity:1;background:#b4b4b4}90%{opacity:1}to{opacity:0}}@keyframes s3ani{0%,10%{opacity:0;transform:rotateX(-179deg)}20%,90%{opacity:1;transform:rotateX(0)}40%{background:#ddd}45%{background:#969696}to{opacity:0}}@keyframes s4ani{0%,20%{opacity:0;transform:rotateX(-179deg)}10%,to{opacity:0}30%{opacity:1;transform:rotateX(0)}40%{transform:rotateX(0);background:#ddd}50%{transform:rotateX(90deg);background:#b4b4b4}80%{background:#b4b4b4}90%{opacity:1;transform:rotateX(90deg)}}@keyframes s5ani{0%,10%{opacity:0;transform:rotateY(-179deg)}20%{opacity:1;background:#ddd;transform:rotateY(0)}40%{transform:rotateY(0)}50%{transform:rotateY(90deg)}55%{background:#ddd}60%{background:#c8c8c8}90%{transform:rotateY(90deg);opacity:1}to{opacity:0}}@keyframes s6ani{0%,20%{opacity:0;transform:rotateY(179deg)}30%{opacity:1;transform:rotateY(0)}40%{transform:rotateY(0)}50%{transform:rotateY(-90deg);background:#ddd}60%,80%{background:#c8c8c8}90%{opacity:1;transform:rotateY(-90deg)}to{opacity:0}}@keyframes half-fold{0%,50%{transform:rotateX(0)}60%,90%{transform:rotateX(-90deg)}}
/* TODO: Fix it */
body {
  font-size: 1rem;
  line-height: 1.5rem;
  font-family: 'Open Sans', sans-serif;
  background: #fff;
  padding: 0 2rem;
}
h1 {
  font-weight: 600;
  margin-bottom: 3rem;
  text-align: center;
  color: #212121;
}
#leadership {
  width: 100%;
  margin: 1rem auto;

  border-collapse: collapse;
  box-shadow: 0 2px 7px rgba(0,0,0,0.2);
  background: #fafafa;
}
#leadership td {
  padding: 1rem .5rem !important;
  text-align: left;
  font-weight: 500;
  transition: all .3s ease-in-out;
}
#leadership tr:hover td{
  background: #03a9f4;
  color: #fefefe;
}
#leadership tr:hover td a {
  color: #fff;
}
#leadership th {
  padding: 1.5rem .5rem !important;
  color: #727272;
  text-align: left !important;
  font-weight: 500;
  border-bottom: 1px solid #dcdcdc;
}
#leadership a {
  text-decoration: none;
  color: #212121;
}
#leadership a:hover {
  color: #03a9f4;
}
#leadership td:nth-of-type(1){
  text-align: center;
  color: #727272;
  font-size: .75rem;
}
#leadership td:nth-of-type(2){
}
#leadership td:nth-of-type(2) img {
  width: 34px;
  border-radius: 50%;
}
/* #leadership th:nth-of-type(1),
#leadership th:nth-of-type(2){
  border-bottom: none;
} */
#leadership th:nth-of-type(5),
#leadership th:nth-of-type(6),
#leadership th:nth-of-type(7),
#leadership td:nth-of-type(5),
#leadership td:nth-of-type(6),
#leadership td:nth-of-type(7) {
  text-align: center !important;
}

<script src="https://mayorovp.github.io/codegolf/97314479fcd24a2386e1.js"></script>
<div class=cssload-container><div class=cssload-cube><div class=cssload-half1><div class="cssload-side cssload-s1"></div><div class="cssload-side cssload-s2"></div><div class="cssload-side cssload-s5"></div></div><div class=cssload-half2><div class="cssload-side cssload-s3"></div><div class="cssload-side cssload-s4"></div><div class="cssload-side cssload-s6"></div></div></div></div>

Удачи всем!

Answer 1

Ruby, 84 91

->a{(1..a.size).flat_map{|n|a.sort.combination(n).select{|c|c.reduce(:+)==10}.uniq}}

Первое решение, которое таки умещается в одну строку при просмотре с сайта!

Это литерал лямбды, который надо вызвать с массивом входных данных. Результатом будет массив из найденных комбинаций.

Ideone

В Ruby функция получения комбинаций элементов массива реализована прямо в классе Array, в стандартной библиотеке. Ой.

В остальном, решение максимально прямое и неплохо переводится на естественный язык:

(1..a.size)              # Для диапазона от 1 до длины массива А
  .flat_map{ |n|         # ...сконкатенировать для каждого N в нём следующее:
    a.sort               #   Из отсортированного массива А...
     .combination(n)     #   ...взять все комбинации длиной N элементов
     .select{ |c|        #   ...выбрав только те С из них, в которых:
       c.reduce(:+)==10} #     Cвёртка С сложением равна 10.
     .uniq}              #   ...убрав повторения.

Поскольку порядок в комбинациях неважен, чтобы не получить дубликатов, массив можно отсортировать. Можно отсортировать и комбинации постфактум, но это медленнее и требует больше символов.

Answer 2

Haskell, 42 70 символа

g=nub.filter((10==).sum).subsequences.sort

Требует импорта функций nub, sort и subsequences из Data.List

Запуск: main = print $ g [5,5,2,3] http://ideone.com/5jUIsy

Как работает:

• входной список сортируется (иначе функция nub, см. далее, не поймет);
• функция subsequences находит все сочетания (без ограничения длины), их 2^m, где m - длина входного списка;
• при помощи filter выбираются те сочетания, которые дают нужную сумму;
• при помощи nub выбираются различные сочетания.

PS спасибо участнику Artem Konovalov за то, что опосредованно подсказал мне не писать велосипед, а заглянуть в стандартную библиотеку языка :)

Answer 3

SQL SQLite Oracle 11.2, 104 114 124 147 176

обнаружен баг (см.комментарии)

Реализация алгоритма выборки комбинации слагаемых для получения заданной суммы из заданного набора значений, с помощью рекурсивных SQL-запросов

• Решение на конкурс

 WITH t(p,w,s)AS(SELECT'',0,0 UNION SELECT p||i||';',r,i+s FROM t,a WHERE r>w)SELECT p FROM t WHERE s=10;

• Подготовка

-- создаём таблицу с данными
CREATE TABLE a (r INTEGER, i INTEGER);
-- заполняем
INSERT INTO a VALUES (1,5);
INSERT INTO a VALUES (2,5);
INSERT INTO a VALUES (3,2);
INSERT INTO a VALUES (4,3);

• Читаемый вариант решения
  в конкурсном убраны алиасы. вместо t.r - w, a.r - r, a.i - i

WITH t (p, r, s) AS
  (SELECT '', 0, 0 -- инициализация кортежа для рекурсии
   UNION
   SELECT 
     p || a.i || ';' , -- сбор строки для вывода
     a.r, -- запоминаем номер строки, чтоб не взять дважды    
     a.i+s -- накопительная сумма
   FROM t, a
   WHERE a.r > t.r -- ограничение - не использовать уже учтенные строки 
  ) 
SELECT p -- вывод комбинаций
FROM t 
WHERE s = 10; --наше конкурсное условие - сумма=10

• Выдача

P
5;5;
5;2;3;   

• Тест (Home - читабельный код, Tab 2 - конкурсный)

Answer 4

perl, 78  &nbsp&nbsp81 95 98 109 112 118 121 123 178

use List::Util 'sum';  # В размере не учитывается - библиотека "из коробки"

sub X{for$c(sort@_){@r=map{$_,[@$_,$c]}@r,[]}grep{!$f{"@$_"}++&&10==sum@$_}@r}

Тест на ideone.com

Не сжатый вариант:

sub X{
 for $c(sort@_) {             # Перебираем отсортированный входной массив
  @r=map {$_,[@$_,$c]} @r,    # Для каждого элемента в массиве вариантов добавляем
                              # такой же но с добавленным текущим числом
                          []  # Затравка первого цикла - пустой массив
 }
 grep {                       # Выбираем те элементы массива
       !$f{"@$_"}++ &&        # Которые еще не встречались ранее
       10==sum@$_             # И сумма элементов которых равна 10
      } @r
}

Старый вариант с рекурсией (95 символов):

sub X {                              # Основная функция
  my$n=pop;                          # $n=первый параметр (текущий остаток)
 @_=sort@_;                          # Сортируем входной массив
 my %r;                              # Объявляем хеш результатов
 map {                               # перебираем массив
  my$a=$n-(my$c=pop);                # вытаскиваем очередной элемент массива (в $c)
                                     # и вычисляем текущий остаток минус данный элемент массива
    $r{"$c,$_"}++ for X(@_,$a)       # Кладем в хеш результатов каждый элемент массива,
                                     # который вернет функция перед которым текущий элемент с запятой
  $r{$c}++ if!$a                     # Если разность 0 - то кладем в результаты само число
 } @_;
 keys%r                              # возвращаем массив результатов
}

# Вызов    
@A=(1,3,4,5,3,3,7,2,7,10);           # Тестовый массив
$,="\n";
print X(@A,10);

Answer 5

JavaScript, 163 148 141 129 124 118 109 92

байткод для конкурса :) Совместное творчество с @Mike .

f=(n,s,c,r=[],i=0)=>{for(s?0:c[r.join()]=r;i<n.length;)f(n,s-n[i],c,[n[i],...r].sort(),++i)}

Пояснения к коду:

var input = prompt('Введите цифры через запятую, к примеру 5,5,2,0,3,4,10,2,56,2,0,8');
input = input ? input.split(',').map(function(v){return parseInt(v);}) : [];
f=(n/входной массив чисел/,
   s/желаемая сумма/,
   c/выходные данные/,
   r=[]/слагаемые - промежуточная переменная/,
   i=0/текущий шаг - промежуточная переменная/)=>{
  /запуск рекурсии, которая обойдёт все комбинации чисел в массиве 
   , комбинация на каждом шаге в аргументе r
   , (желаемая_сумма - сумма_комбинации) : в аргументе s/
  for(
    s?0:c[r.join()]=r;/если сумма == 0 - записываем слагаемые в выходные данные/
    i<n.length;/рекурсия останавливается, когда доходим до последнего элемента/
  )
  f(n,
    s-n[i]/вычитаем из суммы текущий элемент массива/
    ,c
    ,[n[i],...r].sort()/добавляем в слагаемые текущий элемент массива, сортируем для уникальности/
    ,++i/повторяем операцию для следующего элемента массива/)
}
var output = {};
f(input, 10, output);
alert('Комбинации, дающие 10: ' + Object.keys(output).join('; '));

Тест обфускации:

var input = prompt('Введите цифры через запятую, к примеру 5,5,2,0,3,4,10,2,56,2,0,8');
input = input ? input.split(',').map(function(v){return parseInt(v);}) : [];
f=(n,s,c,r=[],i=0)=>{for(s?0:c[r.join()]=r;i<n.length;)f(n,s-n[i],c,[n[i],...r].sort(),++i)}
var output = {};
f(input, 10, output);
alert('Комбинации, дающие 10: ' + Object.keys(output).join('; '));

P.S. Вариант для конурса имеет избыточные аргументы для краткости:
Вторым аргументом необходимо передать желаемую сумму, в нашем случае 10.
Третий аргумент - объект, в который запишется результат, экономия на return надеюсь разрешена)

Answer 6

R, 111

s<-function(a)unique(Filter(function(x)sum(x)==10,unlist(Map(function(n)combn(a,n,sort,F),c(1:length(a))),F)))

Код на IDE ONE

Человекопонятный код:

solve <- function(a) {
  # собираем вектор с допустимыми длинами комбинаций
  sizes <- c(1:length(a)) 
  # сопоставляем каждой длине комбинации, получаем список списков комбинаций, каждая комбинация пропускается через sort
  combinations <- Map(function(size) combn(a, size, FUN = sort, simplify = FALSE), sizes)
  # делаем список с комбинациями плоским
  combinations <- unlist(combinations, recursive = FALSE)
  # оставляем только комбинации дающие в сумме 10
  combinations <- Filter(function(x) sum(x) == 10, combinations)
  # выкидываем дубликаты
  combinations <- unique(combinations)
  #возвращаем результат
  combinations
}

Вызывется на интересующем векторе

s(c(2,3,5,5))

Answer 7

PHP, 114   120 127 130 131 132 143 151 140 142 145 149 163 171 172

По количеству так-же, но выдает меньше предупреждений и работает быстрее.

function($a,&$o){for(;2e3-$c++;$d&=$t=[])foreach($a as$k=>$e)1<<$k&$c?:($d+=$t[]=$e)-sort($t)-9?:$o[join($t)]=$t;}

sandbox

function($a, &$o){
    for(; 2e3 - $c++; $d &= $t = [])                 // Перебор битовых масок массива 0..1023(2000)
        foreach($a as $k => $e)
            1<<$k&$c                                 // Попадает ли элемент в маску?
                ?: ($d += $t[] = $e) - sort($t) - 9  // sort() == 1,  ($d += $t[] = $e) == $d
                    ?: $o[ join($t) ] = $t;          // join совместно с sort обеспечивают уникальность
}

Answer 8

Python3, 130         131 136 144 147 168 182 216 226

Минифицированный вариант:

def r(a,c=[],z=[]):
 a.sort()
 for i,v in enumerate(a):z+=[c+[v]]if v+sum(c)==10*0**(c+[v]in z)else r(a[i+1:],c+[v],z)*0
 return z

Пример использования:

res = r( [1,4,5,5,2,3,1,4] )
print( res )

Минифицированная версия исключительно для гольфа.

---

Не минифицированная версия:

def recur( arr, curArr, maxSumm ):
    arr.sort()
    curSumm = sum( curArr ) # текущая набранная сумма, не забываем, что sum([]) == 0
    result = []
    for i in range( len( arr ) ):
        if arr[i] + curSumm == maxSumm: # если в сумме набрали нужное число, то добавляем к результату
            result+=[ curArr + [ arr[i] ] ]
        elif arr[i] + curSumm < maxSumm: # если сумма меньше, то добавляем результат рекурсивного вызова
            result+= recur( arr[i+1:], curArr + [ arr[i] ], maxSumm )
    return result

def unique( arr ): # уникальные значения массива
    unique = []
    [ unique.append(i) for i in arr if i not in unique ]
    return unique

Живой пример:
http://ideone.com/ggl9lO

Answer 9

Javascript ES6, 165 161 150 147 145 134 133 125 123 (неверно) 124 118

a=>[...Array(2e3)].map((x,q)=>a.filter((x,i)=>q&1<<i).sort()).sort().filter((x,i,a)=>x+""!=a[i-1]&eval(x.join`+`)==10)

Примечания:

1. Длина массива ограничена 10 числами, поэтому можно использовать перебор по маске.
2. Лямбда-функция не рекурсивная, поэтому её сохранение в переменную не учитывается в числе символов. Подробнее на codegolf'е.
3. Текущая версия функции не создаёт глобальных переменных

Проверка:

f=a=>[...Array(2e3)].map((x,q)=>a.filter((x,i)=>q&1<<i).sort()).sort().filter((x,i,a)=>x+""!=a[i-1]&eval(x.join`+`)==10)
console.log(f([5,5,2,3]).join("   "))
console.log(f([5,2,3]).join("   "))
console.log(f([0,10,10,5,0]).join("   "))
console.log(f([0,10,10,5,0,5]).join("   "))
console.log(f([9]).join("   "))

Answer 10

Scala, 69 73, 80

Нечитабельный вариант:

def f(a:Seq[Int])=a.indices.flatMap(a.combinations).filter(_.sum==10)

пример использования

val a = List(1,2,3,4,5,6,7,8,9,10)
println(f(a))

Читабельный вариант:

def getSeq(list: List[Int]) =
 list
  //берем индексы т.е. получаем последовательность от 0 до size
  .indices
  //берем всевозможные комбинации длиной index из элементов списка
  .flatMap(index => list.combinations(index))
  //фильтруем списки по сумме элементов == 10
  .filter(s => s.sum == 10)

Демка

Answer 11

C++, 174 152

using m=multiset<int>;set<m>f(auto a){set<m>r;for(int q=2e3,s;--q;){m c;s=10;for(int&x:a)if(q&1<<&x-&a[0])c.insert(x),s-=x;if(!s)r.insert(c);}return r;}

Примечания:

• В качестве аргумента следует передавать контейнер, в котором элементы лежат последовательно.

http://ideone.com/4AAo0T http://ideone.com/o1nsmz

#include <iostream>
#include <set>
#include <vector>

using namespace std;

//set<multiset<int>>f(vector<int>a){set<multiset<int>>r;for(int q=2e3,s;--q;){multiset<int>c;s=0;for(auto&x:a)if(q&1<<&x-&a[0])c.insert(x),s+=x;if(s==10)r.insert(c);}return r;} //174
//using m=multiset<int>;set<m>f(vector<int>a){set<m>r;for(int q=2e3,s;--q;){m c;s=0;for(auto&x:a)if(q&1<<&x-&a[0])c.insert(x),s+=x;if(s==10)r.insert(c);}return r;} //161
//using m=multiset<int>;set<m>f(auto a){set<m>r;for(int q=2e3,s;--q;){m c;s=0;for(auto&x:a)if(q&1<<&x-&a[0])c.insert(x),s+=x;if(s==10)r.insert(c);}return r;} // 155
//using m=multiset<int>;set<m>f(auto a){set<m>r;for(int q=2e3,s;--q;){m c;s=0;for(int&x:a)if(q&1<<&x-&a[0])c.insert(x),s+=x;if(s==10)r.insert(c);}return r;} // 154
//using m=multiset<int>;set<m>f(auto a){set<m>r;for(int q=2e3,s,i;--q;){m c;s=i=0;for(int&x:a)if(q&1<<i++)c.insert(x),s+=x;if(s==10)r.insert(c);}return r;} // 153
//using m=multiset<int>;set<m>f(auto a){set<m>r;for(int q=2e3,s,i;--q;){m c;s=10,i=0;for(int&x:a)if(q&1<<i++)c.insert(x),s-=x;if(!s)r.insert(c);}return r;} // 153
  using m=multiset<int>;set<m>f(auto a){set<m>r;for(int q=2e3,s;--q;){m c;s=10;for(int&x:a)if(q&1<<&x-&a[0])c.insert(x),s-=x;if(!s)r.insert(c);}return r;} // 152
//using m=multiset<int>;set<m>f(auto a){set<m>r;m c;for(int q=2e3,s;--q;!s?r.insert(c),0:0){c.clear();s=10;for(int&x:a)if(q&1<<&x-&a[0])c.insert(x),s-=x;}return r;}

int main()
{
    for (auto &r : f((vector<int>){5,5,2,3}))
    {
        for (auto &x : r)
            cout << x << ' ';

        cout << '\n';
    }

    return 0;
}

Answer 12

Java, 1437

Всем добрый день. Не уверен, есть ли однозначность в условии, но насколько я понимаю, если входной массив {2, 3, 5, 5, 0}, то в результате должно быть 4 строки: {2, 3, 5}, {0, 2, 3, 5}, {5, 5}, {0, 5, 5}. Так как массивы {2, 3, 5} и {0, 2, 3, 5} отличаются один {0}, но массивы разные и их сумма равна 10. В некоторых решениях выше при вводе данных {2, 3, 5, 5, 0} ответ будет только из двух массивов {2, 3, 5} и {5, 5}. Написано, Что во входном файле числа от 0 до 1000 включительно, значит нули могут быть.

Написал свое решение на Java. Оно по сравнению с другими очень громоздкое, однако не хранит список массивов в памяти, чтобы удалять дубликаты, а выводит их "на лету", что называется. Плюс учитывает тот случай, который рассмотрел выше. Большой объем кода еще объясняется написание без использования каких-то стандартных коллекций. Идея в том, чтобы подсчитать количество единиц, двоек, троек и т. д. десяток во входном файле. Зная эту информацию, а также количество нулей, построить ответ.

Рабочий код тут: http://ideone.com/mwV9Uh

Листинг решения:

import java.util.Scanner;
public class Main {
    int c[] = new int[11];
    void f(int n, int s, int[] cc) {
        for (int i = 1; i <= c[n]; ++i) {
            cc[n] += i;
            s += i * n;
            if (s == 10) {
                for (int z = 0; z <= c[0]; ++z) {
                    for (int j = 0; j < z; ++j) {
                        System.out.print("0 ");
                    }
                    for (int j = 1; j <= 10; ++j) {
                        for (int k = 0; k < cc[j]; ++k) {
                            System.out.print(j + " ");
                        }
                    }
                    System.out.println("");
                }
            }
            if (s >= 10) {
                cc[n] -= i;
                return;
            }
            for (int m = n + 1; m <= 10; ++m) {
                f(m, s, cc);
            }
            s -= i * n;
            cc[n] -= i;
        }
   }
   void g() {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int x = scanner.nextInt();
            if (x >= 0 && x <= 10) {
                c[x]++;
            }
            if (x == -1) {
                break;
            }
        }
        int[] cc = new int[11];
        for (int i = 1; i <= 10; ++i) {
            f(i, 0, cc);
        }
   }
   public static void main(String[] args) {
        Main x = new Main();
        x.g();
   }
}

Вот пример читаемого кода:

    import java.util.Scanner;

    public class Main {

        //количество каждого числа от 0 до 10 во входном файле
        int cnt[] = new int[11];

        //вывод массива на экран
        private void printArray(int[] curCnt) {
            for (int i = 1; i <= 10; ++i) {
                for (int j = 0; j < curCnt[i]; ++j) {
                    System.out.print(i + " ");
                }
            }
            System.out.println();
        }

        //перебор для вывода вариантов
        private void brute(int number, int curSum, int[] curCnt, int tab) {
            for (int i = 1; i <= cnt[number]; ++i) {
                curCnt[number] += i;
                curSum += i * number;
                if (curSum == 10) {
                    for (int cntZero = 0; cntZero <= cnt[0]; ++cntZero) {
                        for (int i_ = 0; i_ < cntZero; ++i_) {
                            System.out.print("0 ");
                        }
                        printArray(curCnt);
                    }
                }
                if (curSum >= 10) {
                    curCnt[number] -= i;
                    return;
                }
                for (int newNumber = number + 1; newNumber <= 10; ++newNumber) {
                    brute(newNumber, curSum, curCnt, tab + 1);
                }
                curSum -= i * number;
                curCnt[number] -= i;
            }
        }

        private void run() {
            //считывание данных из консоля
            Scanner scanner = new Scanner(System.in);
            while (scanner.hasNext()) {
                int x = scanner.nextInt();
                if (x >= 0 && x <= 10) {
                    cnt[x]++;
                }
                if (x == -1) {
                    break;
                }
            }
            int[] cntCur = new int[11];


      for (int i = 1; i <= 10; ++i) {
            brute(i, 0, cntCur, 0);
        }
    }

    public static void main(String[] args) {

        Main solution = new Main();
        solution.run();
    }
}

Answer 13

D, 110

import std.stdio;
import std.array;
import std.range;
import std.algorithm;

alias f=e=>e.permutations.map!"a.length.iota.map!(b=>a[0..b+1].array.sort)".join.sort.filter!"a.sum==10".uniq;

void main()
{
    [5, 5, 2, 3].f.writeln;
    [5, 5, 2, 3, 2, 4, 7, 3].f.writeln;
}

Answer 14

Python3, 120

def f(a,o,i=0,p=[]):s=sum(p);exec(('o+=([p],[])[p in o];'*(s>9)+'f(a,o,i+1,sorted(p+[a[i]]));i+=1;'*(len(a)-i))*(s<11))

Примечание

• Результат записывается в параметр функции, т.е. вызываем функцию в виде f(input_list_of_numbers, output_list_of_combinations)

Тест на Ideone

Расшифровка кода

def f(a, o, i=0, p=[]):
    s = sum(p);
    if s < 11:
        if s > 9:
            if p not in o:
                o += [p]
        while i < len(a):
            f(a, o, i + 1, sorted(p + [a[i]]))
            i += 1

Answer 15

Scala

(1 to 10).map(i => List.fill(i)((1 to 10).toList).flatten.combinations(i).count(_.sum == 10)).sum

Решение, учитывающее варианты типа [ 1+ 1+ 1+ 1+ 2 +2 +2]

В условии говорится "Уже выбранные числа могут использоваться неоднократно" но, например, выйгравший вариант на скале не выводит вариант [ 1+ 1+ 1+ 1+ 2 +2 +2] и ему подобные