Generate all possible unique combinations of positive numbers these have sum equal to N

Question

This is my function to generate all possible unique combinations of positive numbers these have sum equal to N.

For example:

• If the input is 4

• The output should be: [ '4', '1+3', '1+1+2', '1+1+1+1', '2+2' ]

You can try it online here

const f=n=>{ // n is a positive number
  if(n==0) return ["0"]
  if(n==1) return ["1"]
  if(n==2) return ["0+2", "1+1"]
  const result = [n+"+0"]
  for(let i=n-1; i>=n/2|0; i--){
    for(const x of (f(n-i) || [])) {
      for(const y of (f(i) || [])) {
        result.push(y + "+" + x)
      }
    }
  }

  // Remove duplicated records
  const map = result.map(v=>v.split`+`.filter(x=>+x>0).sort((m,n)=>m-n).join`+`)
  return [...new Set(map)]
}

//Testing
a=f(8)
console.log(a)

My approach is using recursion, it works like that:

• If I can find all possible unique combinations of positive numbers these have sum equal to N.

• Then I can find all possible unique combinations of positive numbers these have sum equal to N + 1.

For example:

• If all possible unique combinations of positive numbers these have sum equal to 3 are: ["3", "1+2", "1+1+1"] and all possible unique combinations of positive numbers these have sum equal to 2 are ["2", "1+1"]

• Then for 4 it should be:

1. 4 + 0 or 4

2. All possible unique combinations of combinations of positive numbers these have sum equal to 3 and 1

// for 3 it's combinations is
["3", "1+2", "1+1+1"]
// for 1 it is
["1"]

3. All possible unique combinations of combinations of positive numbers these have sum equal to 2 and 2,

// for 2 it's combinations is
["2", "1+1"]

And I only do the loops to the integer of n/2 to avoid duplicatings.

Could you please help me to review it?

const f=n=>{ // n is a positive number
  if(n==0) return ["0"]
  if(n==1) return ["1"]
  if(n==2) return ["0+2", "1+1"]
  const result = [n+"+0"]
  for(let i=n-1; i>=n/2|0; i--){
for(const x of (f(n-i) || [])) {
  for(const y of (f(i) || [])) {
    result.push(y + "+" + x)
  }
}
  }

  // Remove duplicated records
  const map = result.map(v=>v.split`+`.filter(x=>+x>0).sort((m,n)=>m-n).join`+`)
  return [...new Set(map)]
}

//Testing
a=f(8)
console.log(a)

Answer 1

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;
    }
}

Answer 2

• Your code does not perform very well, I suppose because of the double recursion within the f-method.
• It lacks readability: let's say you return to this code a year later: how long would it take to understand what you actually wanted to do?
• Always use strict equality comparison (n == 0 => n === 0).

Readability can at least be enhanced by interpunction, usage of spacing/indents, semicolons and brackets. Omitting semicolons may bite you.

Indentation and brackets make the code more readable. For example:

if(n==0) return ["0"]

is better readable with interpunction:

if (n === 0) {
  return ["0"];
}

Or:

[...].join`+`

May work, but join is an Array method, so it's more clear to use [...].join("+")