javascript - 演算法：給一個數字，求有多少種方法相加等於這個數？

Question

例如8，可以有 4加4，2加5加1等，共有多少種方式，並列出所有方式集合

Answer 1

1. 實數無解

2. 負數無解

3. 如果數字的個數一定很簡單，兩個的話枚舉一半即可，多個可以參考下面的演算法，修改為固定長度即可

4. 如果數字的個數不一定，則也不能存在 0；參考一下

以公式的長度來遍歷遞歸，因為可以剪枝，效率可觀

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']

一開始想到的方式，將 1~n 每個的公式結果緩存起來遞歸，存起來很浪費空間，反覆遍歷也很慢

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

如果是實數.. 這題沒什麼意義

寫個兩兩相加的

這裡寫個遞歸把.. 我也只懂一點點遞歸。 。

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

無解只是你沒有給足條件，正整數是可以做的。用最簡單的遞歸，時間複雜度是接受不了的。用n=100程式直接就崩了
我用的動態規劃，用一個矩陣保存s[i,j]保存對應的結果，這樣就不需要每次都重新算出之前的結果。
其中si,j，i=n,以j開頭的組合數量，因為沒有0的情況，所以是s[i,0]我放的是s[i,1]+s[i,2]+. ..+s[i,j]的結果
例如s[5,1]，就是表示n=5，1+1+1+1+1，1+1+1+2，1+1+1+ 3，1+1+1+4，1+2+2,5種情況，
其實按照這種方式可以很容易看出s[i,1]=s[i-1,0]，故
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]
其中我們去掉重複的條件，就只需要計算到s[i,i],
s[i,0]=s[i-1,0] +...+s[i,i]
由於s[i,i]=1，所以最後只需要計算出
s[i,2]+s[i,3]+...+s[i ,i-1]的結果
由於後來的數的組合方式都可以重之前的組合拼接出來，
同s[i,1] = s[i-1,0],
s[i,j] = s[i-j,k],其中j > 1, j <= k <= i
下面是偽代碼

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
}

下面是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]++;
    }
}

感覺還可以再優化，計算si,j>1的情況可以預先保存之前組合的數量，透過空間換時間。
希望對你有幫助

Answer 4

這個東西有一個函數叫拆分函數P
我之前做過一個跟這個有關的小算法題神的90億名字
不過我的題目中只需要求出整數拆分的數目，沒有涉及具體的組合，在上面那篇分割函數P中估計有涉及到

Answer 5

這種演算法邏輯最好有一定的限定條件，我姑且認為有指定數量的元數字和目標數字。

Java版本：

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#版本：

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版本：

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版本：

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

如果給定條件是正數的話，把陣列換成1~N。這個邏輯同樣適用負數。

Answer 6

這個演算法還是比較簡單的
如果要分解的數為雙數比如18 那麼幾乎它的結果會是(18/2+1)種組合然後第一個數從0開始遞增，第二個數從最大值遞減即可
如果為單數17，那麼可以讓它加1後再除以2，又變成（18/2)了，然後第一個數從0開始遞增，第二個數從最大值遞減即可