javascript - Algorithm: Given a number, how many ways can the sum equal to this number?

Question

For example, 8, there can be 4 plus 4, 2 plus 5 plus 1, etc. How many ways are there, and list all the ways together

Answer 1

1. Real numbers have no solution

2. Negative numbers have no solution

3. If the number of numbers must be very simple, if there are two, enumerate half of them. If there are more than one, you can refer to the algorithm below and modify it to a fixed length

4. If the number of numbers is not certain, 0 cannot exist; please refer to it

Traverse the recursion according to the length of the formula, because it can be pruned and the efficiency is considerable

function count (num) {
  if (!(num > 1)) { return [] }

  var equations = []
  var eq = []
  for (let len = 2; len <= num; len += 1) {
    _countByLen(num, eq, 0, len, 0)
  }
  return equations

  function _countByLen (num, eq, i, len, sum) {
    if (i === len) {
      if (sum === num) {
        equations.push(eq.join('+'))
      }
      return
    }

    for (let n = eq[i - 1] || 1; n < num; n += 1) {
      let newSum = n + sum
      if (newSum > num) { break }
      eq[i] = n
      _countByLen(num, eq, i + 1, len, newSum)
    }
  }
}

count(5) // ['1+4', '2+3', '1+1+3', '1+2+2', '1+1+1+2', '1+1+1+1+1']

The way I thought of it at the beginning was to cache 1~n formula results each time recursively. It wastes space and is very slow to traverse repeatedly

function count (num) {
  if (!(num > 1)) { return [] }

  var equations = [,[[1]]]
  _count(num)
  return equations[num].slice(0, -1).map(eq => eq.join('+'))

  function _count (num) {
    if (equations[num]) { return equations[num] }

    let halfNum = Math.floor(num / 2)
    let eqNum = [] // 即 equations[num]
    for (let n = 1; n <= halfNum; n += 1) {
      _count(num - n).forEach(eq => {
        if (n <= eq[0]) {
          eqNum.push([n].concat(eq))
        }
      })
    }
    eqNum.push([num])
    equations[num] = eqNum
    return eqNum
  }
}

count(5) // ["1+1+1+1+1", "1+1+1+2", "1+1+3", "1+2+2", "1+4", "2+3"]

Answer 2

If it is a real number... this question makes no sense

Write a two-by-two addition

Write a recursion here... I only know a little bit about recursion. .

R

var color = ''; 
var wow = (n, i = 0) => {
    if (i > n / 2) return ;
    else {
        console.log(`%c ${n} = ${i} + ${n - i} `, color); 
        wow(n, i + 1); 
    }
}

S

Answer 3

There is no solution just because you didn’t give enough conditions, it can be done with positive integers. With the simplest recursion, the time complexity is unacceptable. The program with n=100 will crash immediately
The dynamic programming I use uses a matrix to save s[i,j] to save the corresponding results, so that there is no need to recalculate the previous results every time.
Among them, si, j, i=n, ​​the number of combinations starting with j, because there is no case of 0, so it is s[i,0]. What I put is s[i,1]+s[i,2]+. The result of ..+s[i,j]
For example, s[5,1] means n=5, 1+1+1+1+1, 1+1+1+2, 1+1+1+ 3, 1+1+1+4, 1+2+2, 5 cases,
In fact, according to this method, it can be easily seen that s[i,1]=s[i-1,0], so
s [i,0]=s[i,1]+s[i,2]+...+s[i,j]
s[i,0]=s[i-1,0]+s[i ,2]+...+s[i,j]
Among them, if we remove the repeated conditions, we only need to calculate s[i,i],
s[i,0]=s[i-1,0] +...+s[i,i]
Since s[i,i]=1, we only need to calculate
s[i,2]+s[i,3]+...+s[i in the end ,i-1] result
Since the subsequent combinations of numbers can be spliced ​​together by the previous combinations,
is the same as s[i,1] = s[i-1,0],
s[i,j] = s[i-j,k], where j > 1, j <= k <= i
The following is the pseudo code

function(s, n) {
    s <= {0,0};
    for(i = 1 to n)
        for (j = 1 to floor(i/2) )
            if(j = 1) 
                s[i][j] = s[i-1][0]
            else 
                temp = 0;
                for(k = j to i)
                    temp += s[i-j][k]
                s[i][j] = temp
                
            s[i][0] += s[i][j]
        s[i][j] = 1,
        s[i][0]++
        
    return s
}

The following is implemented in PHP

function calculate(&$s, $n) {

    for( $i = 1; $i <= $n; $i++ ) {
        $s[$i][0] = 0;
        for( $j = 1; $j <= floor($i/2); $j++ ) {
            //以1开头的，等于上一次计算结果
            if( $j == 1 ) {
                $s[$i][$j] = $s[$i - 1][0];
            } else {
                $temp = 0;
                for ($k = $j; $k <= $i; $k++) {
                    if( isset($s[$i - $j][$k]) ) {
                        $temp += $s[$i - $j][$k];
                    }
                }
                $s[$i][$j] = $temp;
            }
            $s[$i][0] += $s[$i][$j];
        }
        //对角线，加上自身
        $s[$i][$i] = 1;
        $s[$i][0]++;
    }
}

It feels like it can be further optimized. When calculating si,j>1, the number of previous combinations can be saved in advance and time can be exchanged through space.
Hope it helps you

Answer 4

This thing has a function called the split function P
I have done a small algorithm question related to this before: God’s 9 billion names
However, my question only requires the number of integer splits, and does not involve specific combinations , it is estimated to be involved in the above article split function P

Answer 5

This kind of algorithm logic is best to have certain restrictions. I tentatively think that there are a specified number of element numbers and target numbers.

Java version:

import java.util.ArrayList;
import java.util.Arrays;

class SumSet {
    static void sum_up_recursive(ArrayList<Integer> numbers, int target, ArrayList<Integer> partial) {
       int s = 0;
       for (int x: partial) s += x;
       if (s == target)
            System.out.println("sum("+Arrays.toString(partial.toArray())+")="+target);
       if (s >= target)
            return;
       for(int i=0;i<numbers.size();i++) {
             ArrayList<Integer> remaining = new ArrayList<Integer>();
             int n = numbers.get(i);
             for (int j=i+1; j<numbers.size();j++) remaining.add(numbers.get(j));
             ArrayList<Integer> partial_rec = new ArrayList<Integer>(partial);
             partial_rec.add(n);
             sum_up_recursive(remaining,target,partial_rec);
       }
    }
    static void sum_up(ArrayList<Integer> numbers, int target) {
        sum_up_recursive(numbers,target,new ArrayList<Integer>());
    }
    public static void main(String args[]) {
        Integer[] numbers = {3,9,8,4,5,7,10};
        int target = 15;
        sum_up(new ArrayList<Integer>(Arrays.asList(numbers)),target);
    }
}

C# version:

public static void Main(string[] args)
{
    List<int> numbers = new List<int>() { 3, 9, 8, 4, 5, 7, 10 };
    int target = 15;
    sum_up(numbers, target);
}

private static void sum_up(List<int> numbers, int target)
{
    sum_up_recursive(numbers, target, new List<int>());
}

private static void sum_up_recursive(List<int> numbers, int target, List<int> partial)
{
    int s = 0;
    foreach (int x in partial) s += x;

    if (s == target)
        Console.WriteLine("sum(" + string.Join(",", partial.ToArray()) + ")=" + target);

    if (s >= target)
        return;

    for (int i = 0; i < numbers.Count; i++)
    {
        List<int> remaining = new List<int>();
        int n = numbers[i];
        for (int j = i + 1; j < numbers.Count; j++) remaining.Add(numbers[j]);

        List<int> partial_rec = new List<int>(partial);
        partial_rec.Add(n);
        sum_up_recursive(remaining, target, partial_rec);
    }
}

Ruby version:

def subset_sum(numbers, target, partial=[])
  s = partial.inject 0, :+
# check if the partial sum is equals to target

  puts "sum(#{partial})=#{target}" if s == target

  return if s >= target 

  (0..(numbers.length - 1)).each do |i|
    n = numbers[i]
    remaining = numbers.drop(i+1)
    subset_sum(remaining, target, partial + [n])
  end
end

subset_sum([3,9,8,4,5,7,10],15)

Python version:

def subset_sum(numbers, target, partial=[]):
    s = sum(partial)

    # check if the partial sum is equals to target
    if s == target: 
        print "sum(%s)=%s" % (partial, target)
    if s >= target:
        return  

    for i in range(len(numbers)):
        n = numbers[i]
        remaining = numbers[i+1:]
        subset_sum(remaining, target, partial + [n]) 


if __name__ == "__main__":
    subset_sum([3,9,8,4,5,7,10],15)

    #输出:
    #sum([3, 8, 4])=15
    #sum([3, 5, 7])=15
    #sum([8, 7])=15
    #sum([5, 10])=15

If the given condition is a positive number, change the array to 1~N. The same logic applies to negative numbers.

Answer 6

This algorithm is relatively simple
If the number to be decomposed is an even number such as 18, then almost the result will be (18/2+1) combinations. Then the first number increases from 0, and the second number starts from the maximum Just decrease the value
If it is an odd number 17, then you can add 1 to it and then divide it by 2, and it becomes (18/2) again. Then the first number starts to increase from 0, and the second number decreases from the maximum value. That’s it