Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is there any way to determine if a given Sum can be formed by taking minimum number of elements of a set/array.
Repetition of array elements is allowed.I tried brute force taking a map n dovetailing through.
Eg. {1,2,3,4,5}and the sum to be formed is 8. Then {3,5} or {4,4}.
Therefore the size of minimum set is 2,repitition is allowed.
[** Note: Even if you take same element twice it is counted as two.]

share|cite|improve this question
Of course there is a way to determine if a given sum $S$ can be formed by taking a minimum number of elements of a set $X$; just try every one-element subset of $X$, then every two-element subset, and so on, until you get $S$ or know you can never get $S$. So, what's your question, really? – Gerry Myerson Dec 2 '12 at 6:18
I mean is there a way to do it efficiently??Problem is simple incase when duplicates arent wid duplicates complexity increases – nightrider Dec 2 '12 at 6:26
Subset-Sum is the name of a problem where numbers can be taken at most once, which is actually harder than the problem you are describing, so the title is confusing. I'm also not sure what you mean by low cardinality, or how efficient of a solution you are looking for. You're really interested in non-negative solutions to a diophantine equation. – William Macrae Dec 2 '12 at 8:44

1 Answer 1

SUBSET-SUM (mentioned by William Macrae above) reduces to your problem in polynomial time and your problem is NP-complete. you can only look for an efficient heuristic to approximate the solution.

This is rather a comment. only allowing me to write answers here on this site-- not comments. hope this helps.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.