I have array of numbers and I want to find a subarray with given sum, Ive googled a lot but all explanations were for case where subarray is continuous. What if I dont need it to be continuous? how can I find it?
Asked
Active
Viewed 63 times
0
-
usually, a subarray is "continuous", you might want to search for subsets sums – Apr 13 '14 at 20:59
-
2Then the order doesn't matter, and we're talking about the weakly NP-hard subset sum problem. – David Eisenstat Apr 13 '14 at 20:59
-
possible duplicate of [Subset Sum algorithm](http://stackoverflow.com/questions/4355955/subset-sum-algorithm) – Bernhard Barker Apr 13 '14 at 21:14
1 Answers
0
Google for subset sum instead. This is a weakly NP hard problem, meaning it's solvable for integers by a classical dynamic program with runtime proportional to the magnitude of the elements in the set. This is exponential time.
Gene
- 46,253
- 4
- 58
- 96