0

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.

nAku
  • 31
  • 5

1 Answers1

1

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.

exeraph
  • 81
  • 1
  • 8
  • I'm looking to split that array, not just listing all possible variations of subsets. – nAku Jan 07 '18 at 22:20
  • by listing all variations you already split the array (the variations are the new splitted arrays) – exeraph Jan 08 '18 at 02:31
  • Knapsack helped me, it's bin-packing problem what i was looking for. Original post is a bit misleading! – nAku Jan 08 '18 at 06:19