Algorithm of search for conformable numbers [closed]

Let's look at a couple of examples:

Take the number 3. Divide it into a sum of units, the array looks like [1,1,1] .
Next, move the last unit to the first place (in this case, move = addition), it will turn out [2,1,0] , then we will do the same with the next unit to the right, we get [3, 0, 0] . So we got all the combinations of digits, which together give 3. We do not take into account the permutations [2, 1, 0] and [1, 2, 0]

Now let's do the same with the number 5, we get the following sequence of arrays.

 [1,1,1,1,1] [2,1,1,1,0] [2,2,1,0,0] [3,2,0,0,0] [4,1,0,0,0] [5,0,0,0,0] 

The mechanism is the same, except that when we encounter not 1, we subtract 1 from this number and transfer it to the right (in fact, we do the same with 1, therefore we get zeros at the end of the array)

Another example with a bigger number, 8

 [1,1,1,1,1,1,1,1] [2,1,1,1,1,1,1,0] [2,2,1,1,1,1,0,0] [2,2,2,1,1,0,0,0] [2,2,2,2,0,0,0,0] [3,2,2,1,0,0,0,0] [3,3,2,0,0,0,0,0] [4,3,1,0,0,0,0,0] [4,4,0,0,0,0,0,0] [5,3,0...] [6,2,0...] [7,1,0...] 

I think you caught the gist: at each iteration, we take the rightmost nonzero element, subtract one from it, and add it to the left element, which is also considered at iteration

Here is the js code:

 const getNumberTerms = (n) => { if(!n) return [] const result = []; const terms = (new Array(n)).fill(1); result.push([...terms]); let willItterate = true; let last = n - 1; let current = 0; let minCurrent = 0 while(willItterate) { // перемещаем единицу terms[current] += 1; terms[last] -= 1; // добавляем массив в результат result.push([...terms]); // если элемент равен 9, то сдвигаем минимально значение курсора вправо if(terms[current] === 9) minCurrent++ // сдвигаем правый курсор вправо current++; // если самый левый элемент равен нулю, то сдвигаем левый курсор в лево if(terms[last] === 0) last--; // если правый курсор зашел на левый, значит, нужно сбросить его на минимальное значение if(current >= last) current = minCurrent; if(last === minCurrent) willItterate = false; } return result; }; // этот код для презентации const output = document.getElementById('output'); document.getElementById('input').onchange = function () { const result = getNumberTerms(+this.value); output.innerHTML = '' result.forEach(el => { output.innerHTML += `<br>${JSON.stringify(el)}` }) } 

 <input id='input'> <pre id='output'> </pre> 

The complexity of the basic algorithm, it seems to be linear (did not check for sure) Then you can do anything with the answer, whatever. Don't like 0? You can remove them by passing a cycle (though quadratic complexity will be added). Need an array of a certain length? Add zeros at the end, or take the first N items