CODEWITHSUNDEEP
algorithmsearchcombinations
LamaMo
LamaMo

Reputation: 626

Finding the combination of N numbers that their sum give number R

How it would be possible to find/guess the combination of N numbers such as 5 or 7 or whatever that gives a final number R?

For example, determine N = 5 and R = 15

The one possible result/guess that the 5 numbers in which their summation give 15 would be {1,2,3,4,5}

Upvotes: 1

Views: 710

Answers (3)

Dave
Dave

Reputation: 9085

To get n floating point numbers that total a target r:

  1. Fill an array of size n with random numbers in (0,1).
  2. Find the total of the array. Call this T.
  3. Multiply every element in the array by r/T.

-edit (thanks @ruakh) -

  1. To account for floating point error, total the array again, calculate the delta from target, and update the array to correct for it however you like. This will be a very small number. It's probably fine to update the first element of the array, but if you want you could spread it across the full array.

Upvotes: 3

Sơn Ninh
Sơn Ninh

Reputation: 331

Python code

import random
N = 5
R = 7
result = random.sample(range(0, int(R)), N-1)
result.append(R - sum(result))

Upvotes: 0

Jorge Alejandro
Jorge Alejandro

Reputation: 96

This can be solved by backtracking, this is really slow, because it looks for all combinations, but if you only want one combination use K-1 0' and N, this sum = N

n = 15
k = 2
array = [0] * k

def comb (len, sum):
    if len == k - 1:
        array[len] = sum
        print(array)
        return

    for i in range(0, n + 1):
        if sum - i >= 0:
            array[len] = i
            comb(len + 1, sum - i)

comb(0, n)

Upvotes: 0

Related Questions