- Forum
- General C++ Programming
- Sub sums less than IMPORTANT
Sub sums less than IMPORTANT
Hello,
Can somebody help me with an algorithm or idea for this problem :
Given a non sorted data (positive integers), find all groups of elements with sum <= X, where X is given.
ex:[
[2 6 3 1]
X = 8
2+6, 2+3, 2+1, 2+3+1, 3+1, 6+1 ]
I need 3 solutions / algorithms, one that is time efficient, one memory efficient, and a trade-off between the two.
Appreciate any help.
Can somebody help me with an algorithm or idea for this problem :
Given a non sorted data (positive integers), find all groups of elements with sum <= X, where X is given.
ex:[
[2 6 3 1]
X = 8
2+6, 2+3, 2+1, 2+3+1, 3+1, 6+1 ]
I need 3 solutions / algorithms, one that is time efficient, one memory efficient, and a trade-off between the two.
Appreciate any help.
A possible solution would be a recursive algorithm:
To find all sums of elements in a list [a, b, c, d, ...] less than X, find all such sums in [b, c, d, ...] and if they are also less than X-a, duplicate them and add a to the duplicates. Notice that the intermediate list of sums will have to include sums of 1 and 0 elements. You'd have to ignore them when producing the result.
I assume the same algorithm can be implemented in different ways to be space or time efficient.
To find all sums of elements in a list [a, b, c, d, ...] less than X, find all such sums in [b, c, d, ...] and if they are also less than X-a, duplicate them and add a to the duplicates. Notice that the intermediate list of sums will have to include sums of 1 and 0 elements. You'd have to ignore them when producing the result.
I assume the same algorithm can be implemented in different ways to be space or time efficient.
Last edited on
Topic archived. No new replies allowed.