Rearrange numbers in an array to sum a number

I gave an array. And I want to find all permutations of an array so that they add up to specific numbers.
Array a =[2,3,5 ,1]

Target = 8
`Solution: [2,2,2,2], [5,3], [3,3,2], [5,2,1] and all possible combinations. Please provide me with an approach to solve this problem. the problem I am facing is how to deal with repeating elements. Targeting is a large number of 10 ^ 6. I think it is just like This theory


source to share

1 answer

You are faced with a typical Subset Problem . The worst complexity of this problem is exponential, no matter how you express it. You can find good polynomial-time approximations that work wonders for the average case.



All Articles