Problem: Searching N elements from an array which sum is X
You are given S,X and N.
S = size of an array
N = number of elements you have to find
X = sum
You have to find N elements from the array which sum is X.
Input:
7 25 3
1 5 10 7 13 15
Output:
5 7 13
If there are multiple solution you can output any of them. What are the best possible solutions with least complexity for this problem?
S = size of an array
N = number of elements you have to find
X = sum
You have to find N elements from the array which sum is X.
Input:
7 25 3
1 5 10 7 13 15
Output:
5 7 13
If there are multiple solution you can output any of them. What are the best possible solutions with least complexity for this problem?
Last edited on
I don't know if this is the best possible solution, but I guess it isn't that complex, considering that it's the first thing I thought of.
Save the numbers into an array or some sort of STL container. Sort the array/container. Use a recursive function to look through the array/container. The recursive function should take 6 parameters:
the array/container of numbers (pass by address)
a new array/container of numbers to store the numbers you've "found" (pass by value)
an unsigned integer for how far into the first array/container you've checked
the number of elements you still have to find
the current sum of the numbers in the second array/container
the target sum
Save the numbers into an array or some sort of STL container. Sort the array/container. Use a recursive function to look through the array/container. The recursive function should take 6 parameters:
the array/container of numbers (pass by address)
a new array/container of numbers to store the numbers you've "found" (pass by value)
an unsigned integer for how far into the first array/container you've checked
the number of elements you still have to find
the current sum of the numbers in the second array/container
the target sum
Last edited on
Topic archived. No new replies allowed.