In JavaScript, I am looking for a way to discover all potential arrays - consisting of non-negative integers - with a size L that add up to - at most - N:
function findArrays(size, maxSum){}
For example: findArrays(3, 2)
Sample output:
[[0,0,0], [0,0,1], [0,0,2], [0,1,0], [0,1,1], [0,2,0], [1,0,0], [1,0,1], [1,1,0], [2,0,0]]
What I have attempted:
I devised the following strategy:
- Starting from the left, add up the array elements
- If the sum is equal to
Nat positioni:- If the element at the current index is equivalent to
N, reset all the indices prior and increment the subsequent slot - Otherwise: reset previous slots and increment this position
- If the element at the current index is equivalent to
- Else:
- Increase the first available slot
My code snippet:
let getNextArray = (r,L,N)=>{
let sum=0, ind=0, i;
for(i=0; i<L; i++){
sum += r[i];
if(sum===N){
ind = i + (r[i]===N?1:0);
break;
}
}
r[ind]++;
for(i=0; i<ind; i++){
r[i]=0;
}
return r;
};
let findArrays=(L, N)=>{
let arrays=[],r=[],i;
for(i=0; i<L; i++){
r[i] = 0;
}
while(r[L-1]<N){
r = getNextArray(r,L,N);
arrays.push(r.slice());
}
return arrays;
}
While it works for the given input, when calling it with findArrays(5,3), only half (28 / 56) of the solutions are found. Despite my efforts, I suspect it may not be efficient for larger inputs as it computes the sum each time. There has to be a smarter way to achieve this that eludes me..
Previously, I posed a similar question on a more optimal approach, but now I require fixed size arrays. My apologies for the repetition in questioning, yet potentially beneficial for future reference :)
An alternative approach could involve utilizing a method findArrays(size, sum) and iterating through sums 1:N, although my knowledge falls short on implementing this.