Express Any Number As A Sum in Python
This post provides an algorithm to express any number as a sum of other numbers in Python. Prerequisites: Basic idea of recursion and implementation of functions in Python (only for the program implementation). You can refer to Define functions in Python
Express Any Number As A Sum?
This post deals with more of an algorithm than a language-specific implementation (although a python implementation has been included). It explains the algorithm to find all possible combinations to express any positive number as a sum of other positive numbers.
For instance, 3 can be expressed as:
Note that it considers multiple permutations of the same combination of numbers as one single way of expressing i.e 1+2 and 2+1, both represent the same combination.
Also, the algorithm provides all possible combinations of expressing the sum, with the numbers in each combination in ascending order. Eg: 6 can be represented as the sum of 2, 1 and 3. The solution set will contain 1, 2 and 3 in order. This sorted result helps in making further operations on the combinations much easier.
Number as a Sum – The Algorithm
The idea here is to first find the maximum number of numbers one can use to represent the sum (without 0s of course!). For any number n, it is n itself because we can express it as a sum of n number of 1s.
We hence create an array that can hold n number of integers.
We then start a recursive function. The recursive function has the base case of returning the contents of the list if the sum of elements in the list has become n, or exiting the last depth of the recursion through a return statement if the sum has already exceeded n.
When none of the base cases is met, the function finds the immediate previous element in the list (it’s just 1 if we are dealing with the first element). The function always receives an argument that stores the current index in the array we are dealing with. It is 0 when the function is called for the first time. Hence in the function execution for a particular index, we try out all possible numbers for that position starting from the previous element we just found up to the number n. And for each number, we are trying out in that position, we call the function recursively to fill the next index and so on until we equate to or exceed n.
It will be much more clear after the implementation and the sample run
Number as a Sum – Implementation In Python
Consider the following program,
def final_run(arr,ind,n,remain): if remain == 0: #Base case for combination found for i in range(0,ind): print arr[i], print return elif remain<0: #Base case for combination cannot be found further, sum exceeded return if ind==0: #Dealing with the first position in arr prev = 1 else: prev = arr[ind-1] for k in range(prev,n+1): arr[ind] = k final_run(arr,ind+1,n,remain-k) #Recursive Call def all_sums(n): arr = [None for x in range(n)] final_run(arr,0,n,n) all_sums(10)
all_sums() is basically the driver function, which creates an array of the required size and passes relevant arguments for the first call of the recursive function – final_run()
In the final_run() function,
- arr is the array that will be used to find the combinations
- ind is the index for the position we are working on
- n is the target sum
- remain is an argument which contains the value of how much has to be added to achieve the sum. For instance, if we want 5 and we have already filled 1 and 2 in the first 2 positions, remain will hold 5-(1+2) = 2. So the next recursions will find all possible ways to reach 5 using the remaining places in the array
As mentioned earlier, the base cases are first checked. If the sum has been reached, remain will hold 0. Hence we print the contents of the array right up to the ind value. The second base case is hen we have exceeded the required sum and remain holds a negative value. This means that adding any more positive numbers will not give us n as we already have a sum greater than n.
We then find the previous element using (ind-1), but if its the first place we are working on it is 1. This is because 1 is pour starting point in the algorithm. Since we start from the smallest numbers to express the sum and 0 is meaningless, we start with 0
We then run a for loop starting from prev, because if we start from 1, we will have solutions repeated, with just the order of the elements being different i.e 5 will receive both solutions 1+4 and 4+1, both of which are essentially the same combination of elements. Furthermore, starting from prev saves a lot of compilation time as we straight away skip the lower elements. The strategy also helps us get all the results in the ascending order!
So we fill each possibility at the ind position and call the function recursively to fill the subsequent positions after modifying remain (since we have filled a position and incrementing the index
Number as a Sum – Sample Run
Let us take up n=3 simplicity.
When we pass 3 to the driver function, it creates a list that can hold up to 3 elements and passes on the arguments to the final_run() function.
Recursion Depth 1
None of the base cases is met here and ind=0, hence prev is set at 1. A for loop starts from k=1 to k=3. In the first step, list is filled with 1 at index 0
A recursive call is made with arr = [1,None,None], ind=1 and remain=2
Recursion Depth 2
Again no base case is met and prev is set to 1 (arr[ind-1]=arr=1). For loop is run from 1 to prev again and the same recursive call is made again but with arr = [1,1,None], ind=2 and remain=1
Recursion Depth 3
No base case is met and prev is set to 1 again (arr[ind-1]=arr=1). For loop is run from 1 to prev again and the same recursive call is made again but with arr = [1,1,1], ind=3 and remain=0
Recursion Depth 4
Now, base case 1 is met, where remain=0, hence the arr elements are printed from index 0 to 2. That is 1,1,1 is one valid combination. The return statement after that goes back to depth 3
Recursion Depth 3
Now that the function call has returned, the current state is,
arr = [1,1,1], ind=2 and remain=1.
The for loop continues, with k=2. This goes again to depth 4 but meets the second base case, where remain will be -1 since arr=[1,1,2] and sum is 4 which is greater than 3. The same thing happens for all of k=2 to k=3 in recursion depth 3. So it finally exits the for loop and we reach the end of the function. This takes the control back to depth 2
Recursion Depth 2
arr = [1,1,5], ind=1 and remain=2
Even though the last element is 5, it is because of previous recursions and we are not worried about it. Note that the main control of the elements we are considering at a particular time lies with the variable ind. Since ind=1 here, we are worried about the second position currently and are trying out the combinations for that and its subsequent spots.
The same process continues. In the next recursion, 2 will be filled at the second index and the base condition 1 will be met in recursion depth 3 itself
arr=[1,2,5] and ind=2 in recursion depth 3. Hence it displays, 1,2 as a solution
[1,3,5] is an exceeded solution even at up to index 1.
It goes back to depth 1 and here we try 2 in the first position. Note that for the second position we will try only k=2 and k=3 and not 1 again as it will give us a redundant solution as discussed earlier. No solution is found and finally, 3 is tried at position 1 which makes base condition 1 true at depth 2 itself and returns the last solution as 3. Trying any numbers in subsequent positions will only give larger results and all these combinations are terminated at depth 2 itself.
The for loop in recursion depth 1 also terminates after k=3 and the function exits.
The final output is as follows,
Output and Time Consumed
Below are some runs on slightly larger sums. Since printing takes up a lot of the execution time, the results will be stored in an array and only the number of solutions will be displayed. But note that, the same process is being done, except that we are storing the solutions instead of displaying them. It gives us a good estimate of how fast the algorithm is for bigger numbers
About 84 seconds for almost 10 lakh solutions
We basically try all numbers from 1 to n at all the n number of positions for the required combination.
The process is optimised the solution by trying numbers only equal to or greater than the previous position, to avoid redundant solutions. We also terminate the solution the moment the current sum exceeds the required sum i.e remain becomes negative. This reduces the number of recursions by cutting off the moment we realise sum cannot be achieved using further recursions.
Feel free to drop any kind of comments, suggestions or doubts below.