Всем привет! Кросспост из раздела помощь Задача - декомпозировать введенное число на слагаемые всеми возможными способами. Вывести каждый вариант с новой строки. Слагаемые в декомпозиции при выводе должны быть упорядочены в порядке убывания, все варианты надо вывести построчно в лексикографическом порядке, пример: stdin
6
stdout
1 1 1 1 1 1
2 1 1 1 1
2 2 1 1
2 2 2
3 1 1 1
3 2 1
3 3
4 1 1
4 2
5 1
6
Допустимые аргументы в диапазоне от 1 до 40, на выполнение дается 5 секунд. Мой бенчмарк получается таким:
30:   566ms
31:   755ms
32:  1083ms
33:  1416ms
34:  1970ms
35:  2668ms
36:  3604ms
37:  4944ms
38:  6636ms
39:  8936ms
40: 12322ms
Код
package test;

import java.util.*;
import java.util.stream.Collectors;

public class Decompositions {

    private static Map<Integer, Set<Combination>> combinations;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        combinations = new HashMap<>();
        int goal = scanner.nextInt();
        search(goal);
        printCombinations(goal);

//        for (int i = 1; i < 41; i++) {
//            combinations = new HashMap<>();
//            long before = new Date().getTime();
//            search(i);
//            long after = new Date().getTime();
//            System.out.printf("%2d: %5dms%n", i, after - before);
//        }
    }

    private static Set<Combination> search(int element) {
        if (combinations.containsKey(element))
            return combinations.get(element);
        Set<Combination> combinationsOfElement = new HashSet<>();
        combinationsOfElement.add(new Combination(Collections.singletonList(element)));
        for (int i = 1; i <= element / 2; i++) {
            if (element == 1)
                return combinationsOfElement;
            combinationsOfElement.addAll(Combination.merge(search(i), search(element - i)));
        }
        combinations.put(element, combinationsOfElement);
        return combinationsOfElement;
    }

    private static void printCombinations(int goal) {
        combinations.get(goal)
                    .stream()
                    .sorted(Comparator.comparing(Combination::toString))
                    .forEach(System.out::println);
    }

    private static class Combination {

        private final List<Integer> elements;

        public Combination(List<Integer> elements) {
            elements.sort(Collections.reverseOrder());
            this.elements = elements;
        }

        public static Set<Combination> merge(Set<Combination> a, Set<Combination> b) {
            Set<Combination> merged = new HashSet<>();
            for (Combination aCombination : a) {
                for (Combination bCombination : b) {
                    List<Integer> elements = new ArrayList<>(aCombination.getElements());
                    elements.addAll(bCombination.getElements());
                    merged.add(new Combination(elements));
                }
            }
            return merged;
        }

        public List<Integer> getElements() {
            return elements;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (!(o instanceof Combination))
                return false;

            Combination that = (Combination) o;

            return this.elements.equals(that.elements);
        }

        @Override
        public int hashCode() {
            return elements.hashCode();
        }

        @Override
        public String toString() {
            return elements.stream()
                           .map(String::valueOf)
                           .collect(Collectors.joining(" "));
        }
    }
}
Я вижу, что у меня происходят избыточные слияния при поиске всех новых комбинаций из составляющих элементов, но не знаю, как их избежать. Можно было бы обойтись без написания обертки, оставив просто List<Integer>, но было бы непонятнее, а на производительность не влияет, проверял. Может я вообще излишне усложнил, кто может предложить другой вариант перебора?