-4

How would you go about generating all possible permutations of a list of integers, but the sum of the list can never be over the target?

Example:

List of given integers: 1000, 1400, 1054, 2201, 657, 3104, ..

Target: 4000

Output: [1000, 1400, 1054], [2201, 657]

Another possible output would be the following:

Output: [1000], [1400], [1054], ..

Numbers can only be used once, and every number has to be used.

It sounds very similar to the One dimensional Cutting Stock Problem (1D CSP), I want to find a more 'brute force' like answer, instead of a linear programming solution, in order to explore the time disadvantages in big data sets.

M.Kats
  • 21
  • 6
  • These aren't permutations; they are *partitions*. Once you have all the partitions of k groups, for each possible k, you can filter out the invalid partitions (where the target is exceeded). Thus, there are multiple parts to the question; I provided a link for a duplicate of the part that seems like where you're most likely getting stuck. In the future, please try to narrow the focus of questions by *trying to write the code first*, and figuring out what part is actually a problem. – Karl Knechtel May 26 '22 at 22:56
  • 2
    Also: do not tag questions with more than one language, unless your task *must* be solved using code written in *each* language, such that those pieces of code *communicate with each other* in some way. If you have not chosen an implementation language, then unless you are prepared for a [tag:language-agnostic] discussion then you do not have a properly defined question for Stack Overflow yet. – Karl Knechtel May 26 '22 at 23:01
  • @KarlKnechtel OP asked for "permutations" and not "partitions"... Indeed partitions are subset of permutations but counts and way to generate are quite different. – Alexei Levenkov May 26 '22 at 23:02
  • 2
    I know OP asked for permutations. That is, however, **clearly** not the correct word for what is intended, as seen by the given examples. A "permutation" of a list of integers would, necessarily, be a single list (generally speaking, the same integers in a different order), not several lists. – Karl Knechtel May 26 '22 at 23:03

0 Answers0