Q:

Перебор всех возможных вариантов размена суммы на маленькие монеты

У меня было задание сделать программу, которая будет разменивать большую купюру на мелкие монеты. Это у меня худо-бедно получилось. Теперь добавилось условие: чтобы возвращались все возможные варианты размена. И тут я что-то поплыл.   
Как можно модифицировать код, чтобы получить не один вариант размена, а все?
public interface Exchanging {
    Map<Integer, Integer> exchange();
}

public class Exchange implements Exchanging {
    /**
     * Money which should be exchanging.
     */
    private final int sumForExchange;
    /**
     * Nominal coins.
     */
    private final int[] denominationСoins;

    /**
     * Default constructor.
     *
     * @param sumForExchange    money which should be exchanging.
     * @param denominationСoins array with nominal coins.
     */
    public Exchange(final int sumForExchange, final int... denominationСoins) {
        this.denominationСoins = denominationСoins;
        this.sumForExchange = sumForExchange;
    }

    /**
     * Exchange big money on less coins.
     *
     * @return map with coins. Nominal is key, amount coin is value.
     */
    @Override
    public Map<Integer, Integer> exchange() {
        Map<Integer, Integer> result = new HashMap<>();
        int[] coins = sort();
        int residue = sumForExchange;

        for (int i = 0; i != coins.length; i++) {
            ExchangeByValue exchangeByValue = new ExchangeByValue(
                    residue, coins[i]);

            // how much coins content current residue for denominationСoins[i].
            int amountCoin = exchangeByValue.exchange();
            result.put(coins[i], amountCoin);
            // update residue.
            residue = exchangeByValue.getResidue();
        }
        return result;
    }

    /**
     * Sorting array with coins nominal.
     *
     * @return arr sort by descending.
     */
    private int[] sort() {
        int[] result = denominationСoins;
        for (int i = result.length - 1; i >= 0; i--) {
            for (int j = 0; j < i; j++) {
                if (result[j] < result[j + 1]) {
                    int temp = result[j];
                    result[j] = result[j + 1];
                    result[j + 1] = temp;
                }
            }
        }
        return result;
    }

    /**
     * Calculate residue and amount coins.
     */
    private class ExchangeByValue {
        /**
         * Residue for division on coins.
         */
        private final int denomination;
        /**
         * Nominal coin.
         */
        private final int divider;

        /**
         * Default constructor.
         *
         * @param denomination Residue for division on coins.
         * @param divider      Nominal coin.
         */
        private ExchangeByValue(final int denomination, final int divider) {
            this.denomination = denomination;
            this.divider = divider;
        }

        /**
         * @return amount coins which may by get for this.denomination.
         */
        private int exchange() {
            return denomination / divider;
        }

        /**
         * @return residue for future exchange.
         */
        private int getResidue() {
            return denomination % divider;
        }
    }
}

A:

Решение, представленное на Хабре, заключается в том, что количество вариантов набора текущей суммы - это сумма количества вариантов набора меньших сумм, из которых можно получить текущую сумму "докидыванием" одной монеты. Причем номинал монеты должен быть не меньше номиналов монет, входящих в варианты меньших сумм, дабы, например, вариант 1 1 5 не учитывался ещё и как 1 5 1 и 5 1 1.
Сохранение всех вариантов ощутимо усложняет код. В итоге получается так:
Way.java для хранения конкретного варианта размена:
public class Way
{
    private final Integer[] coins;

    public Way()
    {
        coins = new Integer[0];
    }

    public Way(Way way)
    {
        coins = new Integer[way.coins.length + 1];
        System.arraycopy(way.coins, 0, coins, 0, way.coins.length);
    }

    public void add(int coin)
    {
        coins[coins.length - 1] = coin;
    }

    public void print()
    {
        for (int i = 0; i < coins.length - 1; i++)
        {
            System.out.print(coins[i] + " ");
        }
        System.out.println();
    }
}

WaysGroup.java для хранения групп вариантов размена:
import java.util.*;

public class WaysGroup
{
    private final List<Way> ways;

    public WaysGroup()
    {
        ways = new ArrayList<>();
    }

    public void add(Way way)
    {
        ways.add(way);
    }

    public void add(int coin)
    {
        for (Way way : ways)
        {
            way.add(coin);
        }
    }

    public void add(WaysGroup group)
    {
        if (group == null)
        {
            return;
        }
        for (Way way : group.ways)
        {
            ways.add(new Way(way));
        }
    }

    public void print()
    {
        for (Way way : ways)
        {
            way.print();
        }
    }
}

Сам алгоритм в Exchange.java:
public WaysGroup getAllExchanges()
{
    int[] coins = denominationСoins;
    WaysGroup[][] waysGroups = new WaysGroup[coins.length][sumForExchange + 1];
    waysGroups[0][0] = new WaysGroup();
    waysGroups[0][0].add(new Way());
    for (int i = 0; i < sumForExchange; i++)
    {
        for (int j = 0; j < coins.length; j++)
        {
            for (int k = j; k < coins.length; k++)
            {
                if (i + coins[k] <= sumForExchange)
                {
                    if (waysGroups[k][i + coins[k]] == null)
                    {
                        waysGroups[k][i + coins[k]] = new WaysGroup();
                    }
                    waysGroups[k][i + coins[k]].add(waysGroups[j][i]);
                }
            }
            if (i + coins[j] <= sumForExchange)
            {
                waysGroups[j][i + coins[j]].add(coins[j]);
            }
            waysGroups[j][i] = null;
        }
    }
    WaysGroup result = new WaysGroup();
    for (int i = 0; i < coins.length; i++)
    {
        result.add(waysGroups[i][sumForExchange]);
    }
    return result;
}

И, наконец, небольшой тест:
public static void main(String[] args)
{
    Exchange exchange = new Exchange(10, 1, 2, 3);
    WaysGroup allWays = exchange.getAllExchanges();
    allWays.print();
}

Код рассчитан на вывод значений на экран, однако вполне можно добавить getter-ы в Way и WaysGroup для работы с полученными списками монет.

Проведённые оптимизации, которые, возможно, делают код менее понятным:

WaysGroup создаются только при необходимости и удаляются сразу же, как только перестают быть нужными. Это сильно уменьшает затраты памяти и ускоряет работу примерно вдвое.
В Way используется Integer[] вместо ArrayList<Integer>. Благодаря более быстрой обработке public void add(int coin) это ускоряет работу при больших значениях в несколько раз.

A:

А у меня получилось такое решение:
List<Integer> coins = Arrays.asList(1, 2, 5);
coinsChange(10, coins).forEach(System.out::println);

реализация метода
public static List<List<Integer>> coinsChange(int countOfMoney,
                                             List<Integer> coins) {

    Collections.sort(coins);
    List<List<Integer>> result = new ArrayList<>();

    //из лямбды нельзя рекурсивно ссылаться на себя же :(
    class Wrapper<T> {
        private T function;
    }
    Wrapper<Function<Integer, BiConsumer<Integer, List<Integer>>>> recursion = new Wrapper<>();
    recursion.function = money -> (numberOfCoin, buffer) -> {
        if (money < 0 || numberOfCoin < 0)
            return;

        if (money == 0) {
            result.add(buffer);
            return;
        }

        recursion.function.apply(money).accept(numberOfCoin - 1, new ArrayList<>(buffer));
        int coin = coins.get(numberOfCoin);
        buffer = new ArrayList<>(buffer);
        buffer.add(coin);
        recursion.function.apply(money - coin).accept(numberOfCoin, buffer);
    };

    recursion.function.apply(countOfMoney).accept(coins.size() - 1, new ArrayList<>());

    return result;
}

UPD обновил решение, попытался переписать в функциональном стиле, насколько это позволила мне сделать java

