Given a min & max I'd like to find every combination of numbers in that range that add up to a given total using a specified number of bins (reusing numbers is OK). # of bins will approach but not exceed 32, so bitwise is awesome if that's an option.
For example:
input:
min = 1
max = 4
total = 9
bins = 4
output:
1,1,3,4
1,2,2,4
1,2,3,3
2,2,2,3
My crappy, inefficient solution:
function arrSum(arr) {
var sum = 0;
for (var i = 0; i < arr.length; i++) {
sum += arr[i];
}
return sum;
}
function incrementComboArr(arr, maxNum) {
var i = arr.length - 1;
while (i >= 0) {
if (++arr[i] > maxNum) {
i--;
} else {
for (var j = i + 1; j < arr.length; j++) {
arr[j] = arr[i];
}
break;
}
}
return i === -1;
}
getSetCombos = function (minNum, maxNum, target, bins) {
var iters = 0;
var solutions = [];
var arr = [];
var i;
for (i = 0; i < bins; i++) {
arr[i] = minNum;
}
while (true) {
iters++;
var sum = arrSum(arr);
if (sum === target) {
solutions.push(arr.slice());
}
if (incrementComboArr(arr, maxNum)) break;
}
console.log(iters);
return solutions;
};
The problem with my solution is that it increments by 1 even when the delta between the current iteration & the target value is deterministic. Also, it doesn't know when to stop. (I could determine the last feasible solution by doing something like if arr[0] > ~~(total/bins) but that seems wonky. Given that the series is a sequence, I know there has to be some pattern I'm not taking advantage of, but I can't think of it. Code/ideas/lecture notes all welcome!
RESULTS
After converting both answers to ES5 (edits welcome), the first solution clocks in around 5ms & the second one (recursive) around 500ms. I'll mark this as answered in a day.
Here's the code I used for each:
//Code translated from Spektre
subsetSum = function (minNum, maxNum, target, bins) {
var start = new Date();
var solutions = [];
var arr = [];
var i;
var s;
var loop = true;
for (i = 0; i < bins; i++) {
arr[i] = minNum;
}
s = minNum * bins;
while (loop) {
if (s === target) {
solutions.push(arr.slice());
}
for (i = bins;;) {
i--;
arr[i]++;
s++;
for (var j = i + 1; j < bins; j++) {
s+= arr[i]-arr[j];
arr[j]=arr[i];
}
if ((s<=target)&&(arr[i]<=maxNum)) break;
if (!i) {
loop = false;
break;
}
s+=maxNum-arr[i];
arr[i]=maxNum;
}
}
return new Date() - start;
};
//Code translated from karthik
subsetSumRecursive = function(minNum, maxNum, target, bins) {
var start = new Date();
var solutions = [];
var arr= [], i;
var totalBins = bins;
for (i = 0; i < bins; i++) {
arr[i] = minNum;
}
target -= minNum * bins;
countWays(target, bins, arr, 0);
return new Date() - start;
function countWays(target, binsLeft, arr) {
if (binsLeft === 1) {
arr[totalBins-1] += target;
if (arr[totalBins-1] <= maxNum) {
solutions.push(arr.slice());
}
return;
}
if (target === 0 && arr[totalBins-binsLeft] <= maxNum) {
solutions.push(arr.slice());
return;
}
var binsCovered = 0;
if (target >= binsLeft) {
var newArr = arr.slice();
while (binsCovered < binsLeft) {
newArr[totalBins - binsCovered -1]++;
binsCovered++;
}
countWays(target - binsLeft, binsLeft, newArr);
}
countWays(target, binsLeft-1, arr);
}
};
subsetSum(1,4,100,32);
subsetSumRecursive(1,4,100,32);
