Subset Sum Problem
Solution to the Subset sum problem, using dynamic programming with a bottom-up approach.
Algorithm
let numbers:Array<Array<Array<number>>> = []
for (let i = 0; i <= sum; i++) {
numbers.push([])
}
numbers[0].push([])
subset.forEach(number => {
for (let target = number; target <= sum; target++) {
numbers[target - number]?.forEach(combination => {
if (!combination.includes(number)) {
numbers[target].push([...combination, number])
}
})
}
})
let solution = [...(new Set(numbers[sum]))]Example
Subset
8
10
7
2
14
5
4
Sum
10
Solution
10
8
2
Generated numbers
0
1
2
2
3
4
4
5
5
6
2
4
7
7
2
5
8
8
9
7
2
5
4
10
10
8
2