How to find all possible combinations of numbers from 1 to n-1 so that their sum is equal to n?

Question

JavaScript

Good night) I just can’t figure out how to solve the problem ... there is a number, for example 8, you need to find all the numbers from 1 to 7, the sum of which is 8 without repetition ... i.e. lots of options ...
1, 7
2, 6
3, 5
1, 2, 5
1, 3, 4 all options, but it doesn't work very well....
Tell me who solved this, the algorithm for solving the problem, or poke a link))) in Google, as I have not tried to ask a question, it usually gives out a search in an array of a pair of numbers whose sum is equal to n, but I have no limit on how many numbers should be ... maybe 2, or maybe 8 or maybe some more ... you need to somehow go through the array and throw it in until you get the right amount or bust, then roll back and try further, and then I get confused, maybe I’m swarming in the wrong direction ...

Answer 1

Option 1 - complete recursive enumeration. There is one recursive function, which is passed the next number, the current sum and the current list of taken numbers. The function either takes the next number or skips it and is called recursively for the next number. If the amount is too large, it is simply returned immediately. If the sum is n - displays the current numbers and returns.
It is possible to store a list of taken numbers in a global array/list. But you have to carefully roll it back. Before the recursive call, if a new number has been added, then after calling it, remove it from the array / list. So the memory consumption will be O(n) instead of O(n^2).
Something like this:

void Generate(int n, int next, int sum, vector<int> taken) {
  if (next > n || sum > n) return;
  if (sum == n) {
   Output(taken);
  }
  Generate(n, next+1, sum, taken);
  taken.push_back(next);
  Generate(n, next+1, sum+next, taken);
}

...

Generate(n, 1, 0, {});

But this solution will not be the fastest - because it will go into long "dead ends".
Option 2 is an optimized iteration that doesn't iterate over anything extra. First, as in the knapsack problem, when solving dynamic programming, we find all the options to score each amount.
Get a two-dimensional array nx (n+1). d[i][j] will store whether sum j can be collected using numbers from 1 to i.
Base - d[0][0] = true (no numbers - you can dial zero), d[i][0] = false (no numbers. You can't dial zero).
recalculation: d[i][j] = d[i-1][ji] or d[i-1][j] (either we take the current number or not)
Naturally, the first option is considered only if i<=j. You can count this array either with a recursive memory function or just stupidly with two nested loops.
Then we modify our recursive function from the first option. Now it will seem to go from the end and the parameters will be - how many first numbers we can use, how much we should dial and what larger numbers have already been taken. The function again has 2 options - either we take the current number or not. But at the same time, we look in the d[][] array, and can we even dial the required amount with the numbers given to us. If not, we return immediately. When we come to the remaining sum of 0, we display the dialed numbers.
Both solutions have O(2^n) time complexity, but the second one will be several times faster because it doesn't iterate over any dead ends. Perhaps, if you think about it, you can get rid of dynamic programming and generally derive a formula when you can collect a given number k from numbers from 1 to i (maybe there is a formula like i*(i+1)/2 <= k).
If your task is not to display all the sets (there are a lot of them! About 2 ^ n), but to count their number, then there is no need for recursive enumeration, but you can modify dynamic programming, which will instead of true / false count how many ways to collect numbers from i sum j. there will be a formula of the form d[i][j] = d[i-1][j] + d[i-1][ji]. Then the whole solution will be O(n^2) in time and can be done O(n) in memory if you think a little (and store only two or one row of the matrix d).

Answer 2

Binary tree traversal.

Answer 3

If you have a pairing algorithm, just apply it recursively to the elements of the pairs.

Answer 4

works on small ones, there is no way to check on large ones

function* genz( n ){
  for ( let i = n-1; i > 1; i--){
    let a = n - i;
    if (a < i) yield [i,a]
    for (let d of [...genz(a)])
      if (!d.some(value => value >= a || value >= i)) yield [i, ...d]
  }
}

//pretty print
console.log([...genz(13)].map(v=>v.join(' + ')).join('\r\n'), '\r\n');

Answer 5

This option seems to work:

package main

import "fmt"

func sum(s []int) int {
  result := 0
  for _, v := range s {
    result = result + v
  }
  return result
}

func main() {
  n := 10000
  var stack []int
  p := n - 1
  for p > 0 {
    stack = append(stack, p)
    for j := p - 1; j > 0; j-- {
      stack = append(stack, j)
      cur := sum(stack)
      if cur < n {
        continue
      } else if cur == n {
        fmt.Printf("%++v\n", stack)
      }
      stack = stack[:len(stack)-1]
    }
    stack = nil
    p--
  }
}

I'm sorry, I don't write on node.