Review
Your code is a good simple solution. The style is sloppy. The complexity is a bit high and the techniques used are negatively impacting performance.
The template literal call Array.split`+`
always throws me, but I like it; your code reminds me to use it more often.
General points
Delimit all code blocks. Eg if(n==0) return ["0"]
better as if(n==0) { return ["0"] }
Why? JavaScript, like most C style languages, does not require delimited blocks for single statement blocks; however when modifying code it is very easy to overlook the missing {}
.
Use semicolons or be thoroughly familiar with automatic Semicolon Insertion (ASI).
Rather than use continue
consider using the statement } else {
.
Why? continue
breaks the use of indentation that visually helps you see flow in a glance. continue
and its friend break
should be avoided when possible.
// Avoid using continue to skip code
for (a of list) {
if (foo) {
...do something...
continue;
}
...lots of code...
}
// Rather use an else statement
for (a of list) {
if (foo) {
...do something...
} else {
...lots of code...
}
}
Spaces between operators: i>=n/2|0
should be i >= n / 2 | 0
.
When using short circuit expressions (f(n) || [])
use the Nullish coalescing operator
?? eg f(n) ?? []
in rather than logical OR ||
.
In the two inner loops you recurse with the call to (f(n) || [])
. The function f()
always returns an array so there is no need for || []
.
In the innermost loop you recurse on f(i)
for every x
but f(i)
is the same for every x
. This is forcing a lot of redundant processing.
Always move calculations to a level that is One = One, rather than One = Many to avoid unnecessary overhead.
Your inner loop:
for(let i=n; i>=n/2|0; i--){
if(i==n){
result.push(n + "+0")
continue
}
for(const x of (f(n-i)||[])) {
for(const y of (f(i) || [])) { // repeated call to f(i)
result.push(y + "+" + x)
}
}
}
Example of moving the recursive call out of the inner loop:
for (let i = n; i >= n / 2 | 0; i--) {
if (i === n) {
result.push(n + "+0");
} else {
const solvedForI = f(i); // called once only
for (const x of f(n - i)) {
for (const y of solvedForI) {
result.push(y + "+" + x)
}
}
}
}
Tips
Bit-wise divide and floor
Using | 0
to floor Numbers is a handy short cut, but you can divide by a power of 2 and floor in one operation.
Example n / 2 | 0
is the same as n >> 1
. For every left shift you divide by 2 and for every right shift you multiply by two.
(n / 2 | 0) === (n >> 1)
(n / 4 | 0) === (n >> 2)
(n / 8 | 0) === (n >> 3)
(n / 256 | 0) === (n >> 8)
Note that the conversion to uint32 happens before the shift, thus multiplying is not equivalent. Eg 1.5 << 1 === 2
and 1.5 * 2 | 0 === 3
Note Bitwise operations convert to unsigned int32 and thus should only be used for only for numbers in the range \$-(2^{31})\$ to \$2^{31} - 1\$
Cache
You can use a cache to store the results of a function. For recursive functions this can save a lot of processing.
Pseudo-code example of a cache
For positive integer values you can use an Array. For other types of arguments you would use a Map.
// n is a positive integer
function solution(n) { // wrapper
const cache = [];
return recurser(n); // call recursive solution.
function recurser(n) { // n is a positive integer
var result;
if (cache[n]) { return cache[n] } // Return cache if available
while ( ) {
...
recurser(n - val);
/* Some complicated code that adds to result */
...
}
return cache[n] = result;
}
}
Complexity, Performance, & Example
TL;DR
The next part of the answer addresses performance and complexity and how both can be improved with example function.
As the example is a completely different different approach it is not considered a review (rewrite); however some of it can be used in your solution.
Complexity
Your complexity is in the sub-exponential range \$O(n^{m log(n)})\$ where \$m\$ is some value >= 2. This is rather bad. The example reduces complexity by reducing the value of \$m\$.
Performance
Performance is indirectly related to complexity. You can increase performance without changing the complexity. The gain is achieved by using more efficient code, rather than a more efficient algorithm.
Example
The example is a completely different algorithm but some of the techniques can be applied to your solutions, such as the cache and moving the check for found combinations out of the recursing function.
Addressing complexity
I could not modify your algorithm to improve the complexity. This is not due to their not being a less complex algorithm based on your approach, just that I was unable to find it.
Addressing performance
There is a lot of room to improve performance via caching, strings, sorts, and stuff.
Cache
The example uses a cache to reduce calculations. See above Tips regarding cache.
- Note the cache is set up to contain the result of n 0 to 2 which is equivalent to your first 3
if
statements.
Strings
To avoid duplicates you use a Set and because two arrays containing the same values are not the same, you convert the array to a string that can uniquely identify the array content.
However you are manipulating the strings in the inner loops and convert from string to number and back each recursing iteration.
Using the approach of wrapping the recursive function we can avoid the conversion within the main solutions and use the set to filter duplicates once, just before returning the final result.
Sort
Though the sort is not a major part of the complexity, it is where I started when doing the example.
Each iteration adds only one value to the arrays being built. By maintaining the correct order as we go the sort can be avoided completely and we just build the array inserting the new element at the correct position.
The innermost for (const v of sub) {
loop does this inserting the new value to each the sub-arrays returned by the previous recursive solution.
Code Comparison
To gauge the performance and complexity I ran your code as the base and used its results to test the examples' correctness.
I then added counters to both, counting every countable iteration, including under the hood iterations such as those performed by spreads ...
, array map and reverse, string concats, sorts, etc.
The results are as follows.
Counted iterations per tested n
value
n value |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
... 18 |
Your code |
4,834 |
14,179 |
36,630 |
101,818 |
268,192 |
733,260 |
1,947,968 |
277,569,323 |
Example |
333 |
718 |
1,584 |
3,418 |
7,445 |
16,018 |
34,528 |
1,503,242 |
Note The example results may not look that bad as n
increases, however it is still in the same complexity range of \$O(n^{mlog(n)})\$. All I have managed to do is lower \$m\$
Note To match your result I had to add a Array.reverse to the final combinations. The reverse was counted but is not required.
function combos(n) {
const cache = [[], [[1]], [[2], [1, 1]]];
return [...(new Set([...combo(n).map(v=>v.reverse().join`+`)]))];
function combo(n) {
var a = n - 1, b, insert;
if (cache[n]) { return cache[n] }
const res = n % 2 ? [[n]] : [[n], [n >> 1, n >> 1]];
while (a > n - a) {
b = n - a;
for (const sub of combo(a--)) {
const subRes = [];
insert = true;
for (const v of sub) {
v > b || !insert ? subRes.push(v) : (insert = false, subRes.push(b, v));
}
insert && subRes.push(b);
res.push(subRes);
}
}
return cache[n] = res;
}
}
l
(second last line of functionf
) is that meant to beresult
? You should fix the code befor you can get an answer? \$\endgroup\$