Algorithm: Dynamic Sum of n Numbers

Question

Algorithm question

The following array exists list = [1, 3, 6, 8, 12, 18, 25, 28, 30, 40, 45, 50, 60, 68, 78, 88, 98, 128, 158, 198, 248, 298 , 348, 418, 488, 548, 588, 618, 648, 698, 798, 818, 848, 898, 998, 1048, 1098, 1148, 1198, 1248, 1298, 1398, 1448, 149, 8, 1998 , 2298, 2598, 2998, 3298, 3998, 4498, 4998, 5898, 6498], the target value is a number, you need to select the sum of n numbers from list as target, n The range is [1,10], where items in the list allow repeated selection, for example:

Example1: Assuming target = 10,

✅ Possible outcomes are as follows:

• Result 1: 10*1 = 10, => [1,1,1,1,1,1,1,1,1,1]
• Result 2: 1*8 + 2*1 = 10, => [8,1,1]
• Result 3: 1*6 + 3*1 + 1*1 = 10, => [6,3,1]
• Result 4: 3*3 + 1*1 = 10, => [3,3,3,1]
• ...

Example2: Assuming target = 20,

✅ Possible outcomes are as follows:

• Result 1: 18*1 + 2*1 = 20, => [18,1,1]
• Result 2: 12*1 + 8*1 = 20, => [12,8]
• ...

❌ Bad Result:

• 20 1s, against the rules: pick up to 10
• [1,2,5], the sum is not right

Note

• Pick a maximum of 10, a minimum of 1, repeatable picks
• if no suitable result is found, return undefined

Solution

Solution1- Recursive computation - 10/25/2022

Recursion always solves this kind of problem, maybe there are other better ways, I will keep updating and trying.
TypeScript Playground - Recursive computation

Question

I want to find an optimal solution, speed first.

const list = [
    1,
    3,
    6,
    8,
    12,
    18,
    25,
    28,
    30,
    40,
    45,
    50,
    60,
    68,
    78,
    88,
    98,
    128,
    158,
    198,
    248,
    298,
    348,
    418,
    488,
    548,
    588,
    618,
    648,
    698,
    798,
    818,
    848,
    898,
    998,
    1048,
    1098,
    1148,
    1198,
    1248,
    1298,
    1398,
    1448,
    1498,
    1598,
    1648,
    1998,
    2298,
    2598,
    2998,
    3298,
    3998,
    4498,
    4998,
    5898,
    6498,
];

function getCombinations(
    list: number[],
    target: number
): Array<number> | undefined {
  // TODO...
}

Answer 1

This is solvable with dynamic programming. I'll just outline the solution. I do have other posts where I've actually given working code for problems with similar ideas. For example Finding all possible combinations of numbers to reach a given sum.

First imagine we have a 2-D data structure with the following information in each Node:

{
    is_root: true|false,        // True only at the root of the data structure
    current_sum: ...,           // At this node, here is the current sum
    solution_count: ...,        // How many solutions below here
    current_value: ...,         // A value to find more solutions under
    current_value_count: ...,   // How many times this value has been used.
    // First dimension, go back by current_value
    prev_sum_solution: ptr to Node,
    // Second dimension, go back to current sum, previous value
    prev_value_solution: ptr to Node,
}

These nodes will hold ONLY information for solutions. You can report how many there are, or produce the solutions recursively. If node.prev_sum_solution is not null, then node.prev_sum_solution->solution_count gives how many solutions will have current_value next. And if f node.prev_value_solution is not null, then node.prev_value_solution->solution_count gives how many solutions will have current_sum with a previous value next. This allows you to find any particular solution as well.

Now how do we generate this solution? Well first we initialize an array of target+1 pointers to nodes:

solution = [null, null, ..., null]

And then we replace solution[0] with our root node:

{
    is_root: true,
    current_sum: 0,
    solution_count: 1,
    current_value: 0,
    current_value_count: 0,
    prev_sum_solution: null,
    prev_value_solution: null,
}

(Warning. I'll use a mix of notations for this pseudo-code. And specifically . accesses an object's properties, while -> accesses properties from a pointer to an object. You can make the ideas work in any language whether or not it has pointers though.)

And then we go as follows:

for value in list:
    // Add solutions that use this value
    for i in range(n): // ie i is in {0, 1, 2, ..., n-1}
        // We iterate down to avoid solutions that use this.
        for (j = list.length-1; (i+1) * value <= j; j--) {
            this_solution = solution[j]
            prev_solution = solution[j-value]
            if prev_solution == null or
               (prev_solution.current_value != value and 0 < i) or
               (prev_solution.current_value_count != i-i):
               continue // can't add value here.
            else:
                if (this_solution == null) {
                    solution[j] = pointer to Node{
                        is_root: false,
                        current_sum: i,
                        solution_count: prev_solution->solution_count,
                        current_value: value,
                        current_value_count: i,
                        prev_sum_solution: prev_solution,
                        prev_value_solution: null,
                    }
                }
                else {
                    solution[i] = pointer to Node{
                        is_root: false,
                        current_sum: j,
                        solution_count: prev_solution->solution_count + this_solution->solution_count,
                        current_value: value,
                        current_value_count: i,
                        prev_sum_solution: prev_solution,
                        prev_value_solution: this_solution,
                    }
                }
            }
        }

And when we are done, if we have no mistakes, solution[limit] will hold a pointer to a Node that has all the information about all of the possible solutions that exist.