For a given integer a, we find all unique combinations of positive integers that sum up to

Question

No question of homework. I discussed issues here , and I came across this question. Someone answered that. I tried a lot to understand recursion, but I can't get it. Can someone explain this to me?

Write a function for this number, print out all sorts of ways to make this number, using addition and any number equal to or less than this number and greater than zero.

For example, if a = 5 , we have the following seven ways to make 5:

• 1, 1, 1, 1, 1
• fourteen
• 1, 1, 1, 2
• 1, 1, 3
• 2, 3
• 1, 2, 2
• 5

The solution from the site is in 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

When faced with a similar problem, it is often a good idea to take a step back from your editor / IDE and think about the problem by pulling a simple case on the board. Don't even make pseudo-code, just pull out a flowchart of how a simple case (e.g. a = 3 ) for this problem will be the turtle all the way down. Also, don't worry about duplicate combinations at first. Try to find a solution that will give you all the necessary combinations, and then improve your solution so as not to give you duplicates. In this case, why not look at the controlled case of a = 3 ? Let me take a small picture for you. A green checkmark means that we have reached a valid combination, a red cross means that the combination is invalid.

As you can see, we start with three empty subcombinations, and then create three new subcombinations, adding a number to each of them. We want to study all the possible ways, so we choose 1, 2 and 3 and get [1] , [2] and [3] . If the sum of the numbers in the combination is 3, we have found a valid combination, so we can stop to study this way. If the sum of the numbers in the combination exceeds 3, the combination is invalid and we can also stop. If this is not the case, we simply continue to create combinations until we get some valid or invalid solution.

Since your question, apparently, is mainly about how to develop a recursive solution for such problems and less about the specific syntax, and you just managed to find the solution in C ++ that I am going to provide in Python (it almost looks like a pseudo- code, and this is what he knows).

 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, ie 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 

Check the code!

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

This seems to be fine, another test for 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] 

The solution includes all seven combinations that we were looking for, but the code still produces duplicates. As you may have noticed, there is no need to take a number smaller than the previous selected number to create all the combinations. So add code that is just starting to build extcombo for numbers that are not less than the last current number in the combination. If the combination is empty, we simply set the previous number to 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, ie 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 

Check the test code again!

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

The presented solution may not be the most effective that exists, but I hope it will encourage you to think recursively. Break the problem down step by step, pull out a simple case for small inputs, and solve one problem at a time.

Answer 2

Leaving the solution aside for a moment and looking at the problem:

Compare this problem with insertion sorting for an array (or any recursive algorithm). When you insert a sort at any time during runtime, we have part of the sorted array, and the other is unsorted. We select an element from the unsorted part and find it in the sorted part, thereby expanding the sorted part, making the problem smaller.

In the case of this problem, we have a fixed number of elements that we can choose from integers 1 to a number in the problem (let's call it N) to be part of a sequence summing to N.

At any time, we have collected some numbers whose sum is less than N (say, X), reducing the problem to the size of NX, also reducing our choice from 1..N to 1 .. (NX) for the next recursion.

The solution makes it obvious, making every choice from 1 to (NX) and continuing recursively to X = N. Each time the algorithm reaches X = N, it means that a permutation is found.

Note. One of the problems that I see in the solution is that he needs to know the number of permutations that will be found in advance. int a[5]; This can cause problems if this value is unknown.