Decompositions

package stepik.level1.task145;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Date;
import java.util.List;

public class DecompositionsWithArrays {

    private static int amount;
//    private static List<String> combinations;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        amount = Integer.parseInt(reader.readLine());
        long before = new Date().getTime();
//        combinations = new ArrayList<>();

        int[] combination = new int[amount];
        for (int i = 0; i < amount; i++) {
            combination[i] = 1;
        }

        findCombinations(combination);
//        outputResult();
        long after = new Date().getTime();
        System.out.println(after - before + "ms");
    }

    private static void findCombinations(int[] combination) {
        while (true) {
//            combinations.add(combinationToString(combination));
            System.out.println(combinationToString(combination));

            int lastIndex = combination.length - 1;
            if (lastIndex == 0)
                return;

            int indexToIncrease = lastIndex - 1;
            int leftSum = combination[0] + 1;
            for (int i = indexToIncrease; i > 0; i--) {
                if (combination[i - 1] > combination[indexToIncrease]) {
                    leftSum += combination[i];
                } else {
                    indexToIncrease = i - 1;
                }
            }

            int newLength = amount - leftSum + indexToIncrease + 1;
            combination = getNextCombination(combination, indexToIncrease, newLength);
        }
    }

    private static int[] getNextCombination(int[] source, int indexToIncrease, int newLength) {
        int[] nextCombination = new int[newLength];
        for (int i = 0; i < newLength; i++) {
            if (i < indexToIncrease) {
                nextCombination[i] = source[i];
            } else if (i == indexToIncrease) {
                nextCombination[i] = source[i] + 1;
            } else {
                nextCombination[i] = 1;
            }
        }
        return nextCombination;
    }

    private static String combinationToString(int[] combination) {
        StringBuilder builder = new StringBuilder().append(combination[0]);
        for (int i = 1; i < combination.length; i++) {
            builder.append(" ").append(combination[i]);
        }
        return builder.toString();
    }

//    private static void outputResult() {
//        Collections.sort(combinations);
//        for (int i = 0; i < combinations.size(); i++) {
//            System.out.println(combinations.get(i));
//        }
//    }
}