Для заданного целого числа a найдите все уникальные комбинации целых положительных чисел, которые суммируются до

Question

Не вопрос о домашнем задании. Я проходил вопросы here, и я наткнулся на этот вопрос. Кто-то ответил на это. Я много пробовал понять рекурсию, но я не могу ее получить. Может ли кто-нибудь объяснить это мне?

Напишите функцию для данного номера, чтобы распечатать все различные способы сделать это число, используя сложение и любое число, равное или меньшее этого числа и больше нуля.

Например, при a = 5, мы имеем следующие семь способов составляют 5:

• 1, 1, 1, 1, 1
• 1, 4
• 1, 1 , 1, 2
• 1, 1, 3
• 2, 3
• 1, 2, 2

Решение с сайта в C++:

void printSeq(int num , int a[] , int len , int s) 
{ 
    if(num <= 0) 
    { 
     for(int j = 0 ; j < len ; j++) 
      cout << a[ j ] << "," ; 
     cout << endl; 

     return; 
    } 

    for(int i = s ; i <= num ; i++) 
    { 
     a[ len ] = i; 
     printSeq(num - i , a , len + 1 , i); 
    } 
} 

int main() 
{ 
    int a[5]; 
    printSeq(5,a,0,1); 
    cin.get(); 
    return 0; 
} 

Answer 1

Оставляя решение в сторону на данный момент и смотрит на саму проблему:

Сравните эту проблему для вставки сортировки массива (или любой рекурсивный алгоритм). При вставке сортировки в любой момент во время выполнения у нас есть часть отсортированного массива, а другая - несортированная. Мы выбираем элемент из несортированной части и находим его место в сортированной части, тем самым расширяя отсортированную часть, делая проблему меньшей.

В случае этой проблемы у нас есть фиксированное количество элементов, из которых мы можем выбрать из целых чисел 1 в число в задаче (назовем его N), чтобы быть частью последовательности, суммирующей до N.

В любой момент мы собрали некоторые цифры, которые суммируются меньше чем N (скажем, X), уменьшая проблему до размера NX, а также уменьшая наши варианты от 1..N до 1 .. (NX) для следующего рекурсии.

Решение делает очевидным, делая каждый выбор от 1 до (N-X) и продолжая рекурсивно до X = N. Каждый раз, когда алгоритм достигает X = N, означает, что найдена перестановка.

Примечание: Одна из проблем, которые я вижу с решением, заключается в том, что ему необходимо знать количество перестановок, которые будут найдены заранее. int a[5]; Это может вызвать проблемы, если это значение неизвестно.

Answer 2

При столкновении с подобной проблемой часто бывает неплохо сделать шаг назад от вашего редактора/IDE и подумать о проблеме, вытащив простой случай на доске. Даже не делайте псевдокод, просто вытяните блок-схему того, как простой случай (например, a = 3) для этой проблемы будет черепаха полностью вниз. Кроме того, сначала не волнуйтесь о дублированных комбинациях. Попробуйте найти решение, которое даст вам все необходимые комбинации, а затем улучшит ваше решение, чтобы не дать вам дубликатов. В этом случае, почему бы не посмотреть на управляемый случай a = 3? Позвольте мне сделать для вас маленькую картинку.Зеленая галочка означает, что мы пришли к действительной комбинации, красный крест означает, что комбинация недействительна.

Как вы можете видеть, мы начинаем с тремя пустыми субкомбинациями, а затем построить три новых подкомбинации пути добавления номера к каждому из них. Мы хотим изучить все возможные пути, поэтому мы выбираем 1, 2 и 3 и получаем [1], [2] и [3]. Если сумма чисел в комбинации равна 3, мы нашли действительную комбинацию, поэтому мы можем остановиться, чтобы изучить этот путь. Если сумма чисел в комбинации превышает 3, комбинация недействительна, и мы также можем остановиться. Если это не так, мы просто продолжаем строить комбинации до тех пор, пока не получим какое-либо действительное или недействительное решение.

Поскольку ваш вопрос, похоже, прежде всего касается того, как выработать рекурсивное решение для таких проблем и меньше о конкретном синтаксисе, и вам просто удалось найти решение на C++, которое я собираюсь предоставить в Python (это почти выглядит как псевдокод, и это то, что он знает).

def getcombs(a, combo = None): 
    # initialize combo on first call of the function 
    if combo == None: 
     combo = [] 

    combosum = sum(combo) # sum of numbers in the combo, note that sum([]) == 0 
    # simple case: we have a valid combination of numbers, i.e. combosum == a 
    if combosum == a: 
     yield combo # this simply gives us that combination, no recursion here! 
    # recursive case: the combination of numbers does not sum to a (yet) 
    else: 
     for number in range(1, a + 1): # try each number from 1 to a    
      if combosum + number <= a: # only proceed if we don't exceed a 
       extcombo = combo + [number] # append the number to the combo 
       # give me all valid combinations c that can be built from extcombo 
       for c in getcombs(a, extcombo): 
        yield c 

Давайте проверим код!

>>> combos = getcombs(3) 
>>> for combo in combos: print(combo) 
... 
[1, 1, 1] 
[1, 2] 
[2, 1] 
[3] 

Это, кажется, работает хорошо, еще одно испытание для a = 5:

>>> combos = getcombs(5) 
>>> for combo in combos: print(combo) 
... 
[1, 1, 1, 1, 1] 
[1, 1, 1, 2] 
[1, 1, 2, 1] 
[1, 1, 3] 
[1, 2, 1, 1] 
[1, 2, 2] 
[1, 3, 1] 
[1, 4] 
[2, 1, 1, 1] 
[2, 1, 2] 
[2, 2, 1] 
[2, 3] 
[3, 1, 1] 
[3, 2] 
[4, 1] 
[5] 

Решение включает в себя все семь комбинаций мы искали, но код все еще производит дубликаты. Как вы могли заметить, нет необходимости брать число, меньшее, чем предыдущий выбранный номер, для создания всех комбинаций. Итак, добавим код, который только начинает строить extcombo для чисел, которые не меньше последнего текущего числа в комбинации. Если комбинация пуста, мы просто устанавливаем предыдущий номер на 1.

def getcombs(a, combo = None): 
    # initialize combo on first call of the function 
    if combo == None: 
     combo = [] 

    combosum = sum(combo) # sum of numbers in combo, note that sum([]) == 0 
    # simple case: we have a valid combination of numbers, i.e. combosum == a 
    if combosum == a: 
     yield combo # this simply gives us that combination, no recursion here! 
    # recursive case: the combination of numbers does not sum to a (yet) 
    else: 
     lastnumber = combo[-1] if combo else 1 # last number appended 
     for number in range(lastnumber, a + 1): # try each number between lastnumber and a 
      if combosum + number <= a: 
       extcombo = combo + [number] # append the number to the combo 
       # give me all valid combinations that can be built from extcombo 
       for c in getcombs(a, extcombo): 
        yield c 

Еще раз протестируем код!

Представленное решение может быть не самым эффективным, но оно, однако, надеется, что оно побудит вас мыслить рекурсивно. Разбивайте проблему шаг за шагом, вытащите простой случай для небольших входов и разрешите одну проблему за раз.