# 查找总和为 N 或更小的最大大小 L 的所有可能数组的算法

2023-03-18 16:44:27

`function findArrays(maxSize, maxSum){}`

`[[0], [0,0,0], [10,0,0], [1,9], [1,2,3] /*, ... */]`

function getNextArray(r,maxVal){

for(var i=r.length-1;i>=0;i--){

if(r[i]<maxVal){

r[i]++;

if(i<r.length-1){

r[i+1]=0;

}

break;

}

}

return r;

}

function getAllArraysOfSize(size, maxVal){

var arrays=[],r=[],i;

for(i=0;i<size;i++){

r[i]=0;

}

while(r.reduce((a, b) => a + b, 0) < (maxVal*size)){

r = getNextArray(r.slice(),maxVal);

arrays.push(r);

}

return arrays;

};

function findArrays(maxSize, maxSum){

var allArrays=[],arraysOfFixedSize=[],acceptableArrays=[],i,j;

for(i=1; i<=maxSize; i++){

arraysOfFixedSize=getAllArraysOfSize(i,maxSum);

for(j=0; j<arraysOfFixedSize.length; j++){

allArrays.push(arraysOfFixedSize[j]);

}

}

for(i=0; i<allArrays.length; i++){

if(allArrays[i].reduce((a, b) => a + b, 0) <= maxSum){

acceptableArrays.push(allArrays[i]);

}

}

return acceptableArrays;

};

## 2 回答

TA贡献1659条经验 获得超9个赞

function * findArrays(maxSize, maxSum) {

let arr = [];

function * recur(maxSum) {

let k = arr.length;

yield [...arr]; // or: if (k) yield [...arr]

if (k === maxSize) return;

for (let i = 0; i <= maxSum; i++) {

arr[k] = i;

yield * recur(maxSum - i);

}

arr.length = k;

}

yield * recur(maxSum);

}

// demo

for (let arr of findArrays(2, 4))

console.log(JSON.stringify(arr));

function findArrays(maxSize, maxSum) {

let arr = [];

let result = []; // <--- will collect all the subarrays

function recur(maxSum) {

let k = arr.length;

result.push([...arr]);

if (k === maxSize) return;

for (let i = 0; i <= maxSum; i++) {

arr[k] = i;

recur(maxSum - i);

}

arr.length = k;

}

recur(maxSum);

return result;

}

// demo

for (let arr of findArrays(2, 4))

console.log(JSON.stringify(arr));

TA贡献1589条经验 获得超11个赞

const data = [[0],[0,0,0],[10,0,0],[1,9],[1,2,3]];

function findArrays(maxSize, maxSum){

return data.reduce(

(acc, value) => {

if (value.length <= maxSize) {

const tempValue = value;

const sum = tempValue.reduce((acc, val) => val >= 0 ? acc + val : 0, 0);

if (sum <= maxSum && sum > 0) acc.push(value);

}

return acc

}, []

)

}

console.log(findArrays(3, 10));

• 2 回答
• 0 关注
• 9 浏览

0/150