CODEWITHSUNDEEP
algorithmsortingtime-complexity
nAku
nAku

Reputation: 31

Split array of integers to as many as possible sub-arrays with same sum

I'm looking for an algorithm that can split array of integers as many as possible sub arrays with sum of X. I tried to create arrays from hi to low, but at the end I have only left bunch of 2 and its impossible to create subsets with odd sum.

At the moment I'm stuck because I do not know what to look/google for?

eg. Each element can be used once, so all subsets can exist at the same time.

i had an array = [7,6,4,7,8,3,3,7,8,9,4,3,2,6,6,4,2,6] and want to split it in to subsets with sum of 12.

[7,5],[4,8],[9,3],[3,8],[7,3,2],[6,6],[4,2,6]

[7,4] and the surplus.

Upvotes: 0

Views: 423

Answers (1)

exeraph
exeraph

Reputation: 81

This problem is known as the Subset sum problem or more specific the Knapsack problem.

You can find the solution in this question or on this site.

Upvotes: 1

Related Questions