Постановка задачи
Для заданного положительного целого числа target выведите все возможные комбинации положительных целых чисел, которые в сумме дают target число. .
Например, если нам дан ввод ‘5’, это возможные комбинации сумм.
1, 42, 31, 1 , 31, 2, 21, 1, 1, 21, 1, 1, 1, 1
Вывод будет в форме списка списков или массива массивов. Каждый элемент в списке будет другим списком, содержащим возможную комбинацию сумм..
Подсказка
- Рекурсия
- Два списка
Попробуйте сами
- C ++
- C ++
- C ++
- Java
- Java
- Python
- Python
- JavaScript
- JavaScri pt
- Ruby
- Ruby
vector > print_all_sum (int target) {vector > output; //Запись - Ваш - Код return output;}
Решение
- C ++
- C ++
- C ++
- Java
- Java
- Python
- Python
- JavaScript
- JavaScript
- Ruby
- Ruby
void print (vector > output) {for (int i = 0; я > & output, vector & result) {if (target == current_sum) {output.push_back (результат); } для (int i = start; i > print_all_sum (int target) {vector > output; vector результат; print_all_sum_rec (цель, 0, 1, вывод, результат); возврат вывода;} int main (int argc, const char * argv []) {int n = 4; vector > result = print_all_sum (n); print (результат);}
Решение Пояснение
Сложность времени выполнения
Экспоненциальная.
Сложность памяти
Линейная, O (n).
Схема решения
Здесь мы рекурсивно пройдемся по всем возможным комбинациям сумм. Когда текущая сумма равна целевому, мы будем печатать эту комбинацию.
Алгоритм будет рекурсивно проверять все числа, которые могут суммировать до цели . В каждом рекурсивном вызове есть цикл for , который выполняется от start до target . start изначально равен 1 . current_sum — это переменная, которая увеличивается при каждом рекурсивном вызове.
Вот логика кода; каждый раз, когда значение добавляется к current_sum , оно также добавляется в список result , который представляет собой комбинацию сумм для этого конкретного вызова. Когда current_sum становится равным target , мы можем быть уверены, что список result содержит возможную комбинацию для цель . Этот список добавляется к окончательному списку output .
Базовое условие рекурсии: если current_sum равно target, распечатать содержимое вывода
Перед каждым рекурсивным вызовом в result добавляется элемент. Однако после каждого вызова этот элемент также удаляется из списка, чтобы обнулить список.
Давайте запустим этот алгоритм шаг за шагом для примера, где нам нужно найти всю возможную сумму комбинации 4 .
текущая_сумма: 0, начало: 1, результат: [] текущая_сумма: 1, начало: 1, результат: [1] текущая_сумма: 2, начало: 1, результат: [ 1,1] current_sum: 3, start: 1, result: [1,1,1] current_sum: 4, start: 1, result: [1,1,1,1] Добавить к выходу: 1, 1, 1, 1current_sum: 3, start: 1, result: [1,1,1] current_sum: 4, start: 2, result: [1,1,2] Добавить к выходу: 1, 1, 2current_sum: 3, start: 2, результат: [1,2] current_sum: 4, start: 3, result: [1,3] Добавить к выходу: 1, 3current_sum: 2, start: 2, result: [2] current_sum: 4, start: 2, result : [2,2] Добавить к выводу: 2, 2current_sum: 3, start: 3, result: []
