Вывод 3 чисел, которые в сумме дают число n

Question

[Vlad161]

Дано натуральное число n, известно что его можно разбить на сумму 3 неравных 0 чисел.
Написать программу которая выводит все эти числа, но они не должны повторяться, то есть от перемены мест слагаемых, ничего выводится не должно, например число 6, должно выводится 1+2+3 и 2+2+2, вот мой алгоритм

int n = Integer.parseInt(reader.readLine());

        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                for (int k = 1; k < n; k++) {
                     if ((i+j+k) == n) {
                         System.out.println("Числа " + i + " + " + j + " + " +k);
                     }
                }
            }
        }

Но выводит:
Числа 1 + 1 + 4
Числа 1 + 2 + 3
Числа 1 + 3 + 2
Числа 1 + 4 + 1
Числа 2 + 1 + 3
Числа 2 + 2 + 2
Числа 2 + 3 + 1
Числа 3 + 1 + 2
Числа 3 + 2 + 1
Числа 4 + 1 + 1

Догнать не могу как сделать проверку. Написать можно на java или c++, как вам будет удобнее).

П.с. забыл сказать, программа должна решаться только переменными и циклами, то есть никаких коллекций, массивов и т.д.

Answer 1

[Rsa97]

Не должны повторяться перестановки - значит для каждого множества слагаемых {a, b, c} можно найти множество {a', b', c'}, образованное перестановкой элементов исходного множества, такое, что a'<=b'<=c'. Значит каждый следующий вложенный цикл должен начинаться не с 1, а со значения итератора предыдущего цикла.
---
Подумал ещё:
При условии a<=b<=c, a+b+c=n значение a не может быть больше n/3, иначе b либо c будут б̶о̶л̶ь̶ш̶е меньше, чем a.
Значение b не может быть больше, чем (n-a)/2, иначе c будет б̶о̶л̶ь̶ш̶е меньше b.
Значение c будет равно (n-a-b).
Итого, получаем

int n = Integer.parseInt(reader.readLine());
for (int i = 1; i <= n/3; i++) {
    for (int j = i; j <= (n-i)/2; j++) {
        System.out.println("Числа " + i + " + " + j + " + " + (n-i-j));
    }
}

Comments

[Vlad161]

Да, так работает спасибо. Правда я не до конца понимаю, почему оно работает
for (int i = 1; i < n; i++) {
for (int j = i; j < n; j++) {
for (int k = j; k < n; k++) {
if ((i+j+k) == n) {
System.out.println("Числа " + i + " + " + j + " + " +k);
}
}
}
}

[Rsa97]

Потому, что любую тройку чисел {a, b, c} можно отсортировать по возрастанию и привести к одной из неубывающих последовательностей.

Answer 2

[Александр Белов]

Банальный n³ не пройдет.