c - 番号を印刷する方法。与えられた整数を異なる数の合計で表すことができる方法は何ですか？

Question

私が5の数を持っているとすると、5を表すための合計の可能な組み合わせは次のとおりです。

4 + 1

3 + 2

3 + 1 + 1

2 + 2 + 1

2 + 1 + 1 + 1

1 + 1 + 1 + 1 + 1

Cでこのためのプログラムを作成するにはどうすればよいですか？

Answer 1

#include <stdio.h>
#include <stdlib.h>

int *LIST;   /* result work list */
int LEVEL=-1;/* partition level */

void print (void){
    int i;

    for(i=LEVEL;i>=0;--i){
        printf("%d",LIST[i]);
        if(i!=0)
            printf(" + ");
    }
    printf("\n");
}

void part(int n){
    int i, first; /* first is last-1  */

    if(n<1) return ;
    LIST[++LEVEL]=n; /* add list tail */
    print();

    first=(LEVEL==0) ? 1 : LIST[LEVEL-1];

    for(i=first;i<=n/2;i++){ /* candidate > first */
        LIST[LEVEL]=i; /* last element replace */
        part(n-i);
    }
    LEVEL--;
    return;
}

int main(int argc, char **argv){
    int N;

    N=(argc>1)?atoi(argv[argc-1]):5;

    LIST=(int *)calloc(N, sizeof(int));
    if(LIST==NULL){
        fprintf(stderr, "not enough memory\n");
        return -1;
    }

    part(N);
    free(LIST);

    return 0;
}
/* result
5
4 + 1
3 + 1 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1
2 + 2 + 1
3 + 2
*/

Answer 2

別の言い方をしましょう（再帰を助けるために）：

合計が 5 になるすべての異なる組み合わせは、

• 4 + 最大 4 で始まる合計が 1 になるすべての組み合わせ
• 3 + 最大 3 で始まる合計が 2 になるすべての組み合わせ
• 2 + 最大 2 で始まり合計 3 になるすべての組み合わせ
• 1 + 最大 1 で始まり合計 4 になるすべての組み合わせ

Answer 3

Function that returns an array of sets:

Set[] SumComb(int n) {
  If n == 1 return { 1 };
  Set[] ResultN_1 = SumComb(n-1);
  Set[] ResultN;
  for each set S in ResultN_1 {
    Insert { S , 1 } to ResultN
    for each element E in S {
      Let TmpS = S
      Remove E from TmpS
      Increment E
      Add E to TmpS
      Sort TmpS
      Insert TmpS to ResultN if not already inserted
    } 
  }
}