超递增背包算法

题目要求

超递增背包问题：
设$A=(a_1,a_2…,a_3)$是由$n$个不同的正整数构成的$n$元组，且 $a_j>\sum_{j=1}^{j-1}{a_i} (j=2,…,n)$
$S$是另一已知的正整数。
求$A$的子集$A$’，使 $\sum_{a_i \in A’}{a_i}=S$

• 求解算法

  #include <stdio.h>
  #include <stdlib.h>
  #define MAXN 100
  int n,S;
  int a[MAXN],sum[MAXN];
  int ans[MAXN],top;
  void algorithm(int i,int tot) {
      if(tot>S)return; 
      if(i==n) {
          if(tot==S){ 
              printf("找到结果:");
              for (int j = 0; j < top; j++) {
                  printf("%d ", ans[j]);
              }
              printf("\n");
          }
          return;
      }
   if (tot==S) { 
      printf("找到结果:");
      for(int j=0;j<top;j++){
          printf("%d ",ans[j]);
      }
      printf("\n");
      return;
  }
      ans[top++]=a[i]; 
      algorithm(i+1,tot+a[i]);
      top--;
      algorithm(i+1,tot);
  }
  
  int main(){
      printf("请输入A元素个数:");
      scanf("%d", &n);
      printf("请输入S:");
      scanf("%d", &S);
      printf("请输入A中元素:\n");
      for (int i=0;i<n;i++) {
          scanf("%d",&a[i]);
      }
      sum[0]=a[0];
      for(int i=1;i<n;i++) {
          sum[i]=sum[i-1]+a[i];
      }
      printf("找到结果:\n");
      algorithm(0, 0);
      return 0;
  }
  

• 计算复杂度为$O(2^n)$