搞清楚如何循環的方式，（X數之和= Y）

Question

我有一定的困難，這個算法問題。假設您必須使用（x）數量的數量，查找給定總和（y）的所有可能結果。

因此，假設我的x = 3，我的總和是60.我必須找出所有可能的情況。例如 1,1,58,1,2,57等...這有點複雜，但在這裏並不重要。

我可以計算出X = 2，X = 3，但它正在手工完成，我需要弄清楚如何動態地做到這一點。

for ($first=$start; $first <= $highest_number; $first++) { //start = 1, highest_number = y/x which is 20 in this case. 
     for ($inc=$start; $inc <= $end; $inc++) { //end = 40 

      if ($x>= 3) { //assuming x = 3 

       for ($n=$highest_number; $n <= $end ; $n++) { 
        if ($first + $inc + $n == $target) { 
         $result['result'][] = $first .",". $inc .",". $n; 
        } 
       } 

      } else { // assuming x = 2 
       if ($first + $inc == $target) { 
        $result['result'][] = $first .",". $inc; 
       } 
      } 
     } 
    } 

這就是我卡住的地方。所以很明顯，我現在使用的條件爲x = 2，x = 3。什麼是最好的動態做法？我想遞歸函數，我沒有什麼工作，但是這是我想象它看起來：

//recursion - does not work, not sure how to make it work 
    $z = 1; 
    function test($x, $first, $inc){ 
     while ($z<= $x) { 

      //this is where I'm stuck. How do i form my loop so that it works dynamically. 
      for ($n=$start; $n <= $end ; $n++) { 

      } 

     } 
    } 

任何人都可以就如何使其佔任何數量的形成我的遞歸函數的提示x在方程中？

Answer 1

這是NHR組合，其中n = Y，R = X-Y。

#include<iostream> 
#include<map> 
using namespace std; 

class nHr 
{ 
public: 
    nHr(int n, int r) { 
     this->n = n; 
     this->r = r; 
     ar = new int[r]; 
    } 
    int* ar; 
    int n, r; 
    bool next() { 
     ar[r-1]++; 
     int i = r-1; 
     while(ar[i] == n+1) { 
      if(--i == -1) return false; 
      ar[i]++; 
     } 
     while(i < r-1) ar[i+1] = ar[i++]; 
     return true; 
    } 
    int operator[](int n) {return ar[n];} 
}; 

int main(int c, char** v) 
{ 
    if(c < 3) return 0; 
    int x = atoi(v[1]); 
    int y = atoi(v[2]); 
    nHr nhr(y, x-y); 
    map<int, int> m; 
    while(nhr.next()) { 
     for(int i=1; i<=y; i++) m[i]++; 
     for(int i=0; i<x-y; i++) m[nhr[i]]++; 
     for(auto& a : m) cout << a.second << ','; 
     cout << endl; 
     m.clear(); 
    } 
}