0
$\begingroup$

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.]

  • 0
    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?2012-12-02
  • 0
    I mean is there a way to do it efficiently??Problem is simple incase when duplicates arent allowed.bt wid duplicates complexity increases2012-12-02
  • 0
    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.2012-12-02

1 Answers 1