Выведите способы получения заданной суммы повторными бросками игральной кости

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

Input: N = 3
Output: 
1 1 1
1 2
2 1
3
Explanation: The standard dice has 6 faces i.e, {1, 2, 3, 4, 5, 6}. Therefore the ways of getting sum 3 after repeatedly throwing a dice are as follows:
1 + 1 + 1 = 3
1 + 2 = 3
2 + 1 = 3
3 = 3

Input: N = 2
Output: 
1 1
2

Подход: эту проблему можно решить с помощью рекурсии и поиска с возвратом. Идея состоит в том, чтобы выполнить итерацию для каждого возможного значения кости i в диапазоне [1, 6] и рекурсивно вызвать оставшуюся сумму, т. е. ( N – i ), и продолжать добавлять значение текущего значения кости в структуру данных, такую как строки. Если искомая сумма равна нулю, выведите элементы сохраненной строки.

Ниже приведена реализация вышеуказанного подхода

Временная сложность: O(6 ^N )
Вспомогательное пространство: O(1)