0

I have bit stuck trying to implement a combination

for example :

inp = 3

Need combination which could make again the same value like below

`(1,1,1) -> sum -> 3

(2,1) -> sum -> 3

(1,2) -> sum -> 3

(0,3) -> sum -> 3

(3,0) -> sum -> 3`

Not sure how to achieve this. Any idea to start with the approach

nogoriv567
  • 33
  • 4
  • 1
    so you want all the possible combinations for the given input? meaning if it was 21 it would be any possible combination starting from 0, 21 ending with 1,1,1,1,1,1,1,1..... – Saba Nov 28 '22 at 08:02
  • 2
    First you should better describe the problem (since I still don't understand it), then you should solve the problem without programming. Then transcribing the actual algorithm into Python is often very easy. This question is not related to Python but to general problem solving. – Jeyekomon Nov 28 '22 at 08:06

1 Answers1

1

I remember this question. My teacher told me to solve this.

This is the solution:


# arr - array to store the combination
# index - next location in array
# num - given number
# reducedNum - reduced number 


def findCombinationsUtil(arr, index, num,

                              reducedNum):
 

    # Base condition

    if (reducedNum < 0):

        return
 

    # If combination is 

    # found, print it

    if (reducedNum == 0):
 

        for i in range(index):

            print(arr[i], end = " ")

        print("")

        return
 

    # Find the previous number stored in arr[]. 

    # It helps in maintaining increasing order

    prev = 1 if(index == 0) else arr[index - 1]
 

    # note loop starts from previous 

    # number i.e. at array location

    # index - 1

    for k in range(prev, num + 1):

         

        # next element of array is k

        arr[index] = k
 

        # call recursively with

        # reduced number

        findCombinationsUtil(arr, index + 1, num, 

                                 reducedNum - k)
 
# Function to find out all 
# combinations of positive numbers 
# that add upto given number.
# It uses findCombinationsUtil() 

def findCombinations(n):

     

    # array to store the combinations

    # It can contain max n elements

    arr = [0] * n
 

    # find all combinations

    findCombinationsUtil(arr, 0, n, n)
 
# Driver code

n = 5 # This is the Sum
findCombinations(n)
 
# This code is contributed by mits

Note: When my teacher gave me this, I didn’t solve this. I got the code from geeksforgekks.com.

So I’m putting the link to website too: here

Prabhas Kumar
  • 230
  • 10