Reputation: 71
I have a script that gives me all possible combinations of a set of numbers adding up to a number. But I do not want a minimum or maximum number, but I want to be able to enter the numbers I need. So my target could be '3' and the set containing the numbers 1 and 2. As you can see I want also be able to have all possible order and each number can be used more than once. The result in this case would be: 1+1+1, 2+1, 1+2
. I also want the number of results to be displayed.
<!DOCTYPE html>
<html>
<head>
<title>Sum</title>
</head>
<body>
<style>
.table {
display: table;
table-layout: fixed;
width: 100%;
}
.table-row {
display: table-row;
}
.cell {
display: table-cell;
}
</style>
<div class="table">
<div class="table-row">
<div class="cell">Target:</div>
<div class="cell">
<input id="target" type="text" value=15>
</div>
<div class="cell">n:</div>
<div class="cell">
<input id="n" type="text" value=3>
</div>
</div>
<div class="table-row">
<div class="cell">Min:</div>
<div class="cell">
<input id="min" type="text" value=1>
</div>
<div class="cell">Max:</div>
<div class="cell">
<input id="max" type="text" value=12>
</div>
</div>
</div>
<input id="submit" type="button" value="submit" />
<div id="output" />
<script>
function getCombos(target, min, max, n) {
var arrs = [];
if (n === 1 && target <= max) {
arrs.push([target]);
} else {
for (var i = min; i < target / n && i <= max; i++) {
var nextTarget = target - i;
var nextMin = i + 1;
var arrays = getCombos(nextTarget, nextMin, max, n - 1);
for (var j = 0; j < arrays.length; j++) {
var array = arrays[j];
array.splice(0, 0, i);
arrs.push(array);
}
}
}
return arrs;
}
document.getElementById("submit").onclick = function() {
var target = document.getElementById("target").value;
var min = document.getElementById("min").value;
var max = document.getElementById("max").value;
var n = document.getElementById("n").value;
var result = getCombos(+target, +min, +max, +n);
document.getElementById("output").innerHTML = result.join("<br/>");
};
</script>
</body>
</html>
Upvotes: 2
Views: 2175
Reputation: 20414
As pointed out in the comments, this is a version of the subset-sum problem (but instead of summing to 0
, you are summing to some desired number).
The Wikipedia page does give an O(2 ^ (n/2))
, however since your inputs seem small, I will just implement the O(2 ^ N * N)
brute-force algorithm to solve this.
function get_summing_subsets(set_arr, target){
let finish = [];
let working = [[]];
while (working.length){
let next_work = [];
for (let i = 0; i < working.length; i++){
for (let j = 0; j < set_arr.length; j++){
let subset = working[i].concat([set_arr[j]]);
let sum = subset.reduce((a,b) => a + b, 0);
if (sum <= target){
(sum == target ? finish : next_work).push(subset);
}
}
}
working = next_work
}
return finish;
}
which works well:
//your example
get_summing_subsets([1,2], 3)
[[1,2],[2,1],[1,1,1]]
//another
get_summing_subsets([1,2,3], 4)
[[1,3],[2,2],[3,1],[1,1,2],[1,2,1],[2,1,1],[1,1,1,1]]
Upvotes: 3