algorithm - 将正整数分解为更多整数，使得总和与原始整数相同

Question

今天遇到一道面试题，答不出来 正在寻找您的建议

• 一个正整数M的分解是一组唯一的正整数，其和为M
• 例如:7 = 1+6 = 2+5 = 3+4 = 1+2+4

需要编写一个函数来计算所有这些独特的组合

Answer 1

您需要打印它们吗？然后，像这样:

int a[100]; a[0] = 0; //to store composition

void rec(int x, int p) {
   for ( int i = a[p-1]+1; i <= x; i++ )
       if (x - i > i ) {
           a[p] = i;
           rec(x - i, p+1);
        } else {
           a[p] = x;
           //print if needed
           for ( int j = 1; j <= p; j++ )
               cout << a[j] << ' ';
           cout << endl;
           return;
        }
}

然后调用

rec(n, 1);