微软100题第21题解法

问题：输入两个整数n 和m，从数列1，2，3.......n 中随意取几个数,使其和等于m ,要求将其中所有的可能组合列出来.

容器思想：

1.每个物品有两种情况，放或者不放入容器，因此就产生两个子问题，

?也就有两个递归。?

? ? ? ? ? ? ? ? 2.放入容器的话，计算放入后的剩余容量，如果小于0，?说明占满了放弃该数字，如果大于0，那么继续将次大的物体放入容器。递归开始。?

? ? ? ? ? ? ? ? 3.递归推出条件，容器正好被占满。?

?

?

#include <stdio.h>#include <memory.h>void printResult(int *flag, int n){for(int i = 0; i<= n; i++){if(flag[i] == 1)printf("%-3d", i);}printf("\n");}void helperNum(int n, int m, int index, int *flag){if(m == 0)printResult(flag, n);if(index < 1 || m < 1)return;//分为两个子问题，采用该数字和不采用该数字。标志为应用该数字。 flag[index] = 1; helperNum(n, m - index, index - 1, flag);flag[index] = 0;//标记为不应用该数字helperNum(n, m, index - 1, flag);}void findNum(int n, int m){if(n > m)n = m;int flag[n];memset(flag, 0, (n + 1)*sizeof(int));helperNum(n, m, n, flag);}int main(int argc, char *argv[]){//findCombination(4,5);findNum(4, 10);return 0;}