1.cpp

子集和问题.rar:这是我学算法设计时的总结,包括定长和不定长做法(也就是回朔法,剪枝限界),当然也包括穷举法.

/*这回才是真的“不过是用了递归而已”，上一个算法其实是错的：（
  递归思想：对每一个元素，有选取和不选取两种可能。相当于完全二叉树遍历，但当以求得的和大于90时，就不会在遍历那个子树了,还是能省掉很多不必要的操作的。若在release模式下编译，函数调用的开销也不是很大。
  另外还有一个好处就是当集合元素个数大于32个时，本算法还能很好的工作，而以int型变量的二进制位作为指示的方法就要做较大改动。
*/

#include "stdio.h"

int set[10]={10,20,24,25,26,30,34,35,40};
int stack[10];
int top = 0;

void out(void){
  int i = top; 
  while(i)printf("%d ", stack[--i]);
  printf("\n");
}

void fn(int sum,int num){
   if(sum == 0){
     out();
     return;
   }

   if(sum < 0 || num < 1)return;
   
   num--;
   fn(sum,num);

   stack[top++] = set[num];
   fn(sum - set[num], num);
   top--;   
}

void main(){
  fn(90,9);
}