子集(回溯)

时限：1000ms 内存限制：10000K  总时限：3000ms

描述：

有一集合中有 N 个元素，每个元素均为自然数。给定一个 total，求满足条件的所有子集，子集中各元素之和应等于total。

输入：

第一行一个整数表示有N个元素。
第二行N个整数，表示集合里的每个元素。
第三行一个整数表示给定的total。

输出：

输出所有的子集。
每行输出一组可行的子集。每个元素之间有一空格，元素按从小到大排序。

输入样例：

6
1 2 3 4 7 10
4

输出样例：

1 3
4

#include<stdio.h>
int Arr[100]={0};//存放是否将第i个数选入子集
int n,num[100],total;//初始化的三组数据
void search(int m);
void checkmax();
void selection_sort(int Array[],int N);
int main()
{
    int i;
    scanf("%d",&n);//n个数
    for(i=0;i<n;i++)
        scanf("%d",&num[i]);
    selection_sort(num,n);
    scanf("%d",&total);//total
    search(0);
    return 0;
}
void search(int m)//0,1,2....n
{
    if(m==n)
        checkmax();
    else
    {
        Arr[m]=1;//取第m个数
        search(m+1);
        Arr[m]=0;//不取第m个数
        search(m+1);
    }
}
void checkmax()
{
    int sum=0;
    int temp[100],t=0;
    for(int i=0;i<n;i++)
    {
        if(Arr[i]==1)
        {
            sum+=num[i];
            temp[t++]=num[i];
        }
    }
    if(sum==total)
    {
        printf("%d",temp[0]);//输出子集中的第一个数
        for(i=1;i<t;i++)
            printf(" %d",temp[i]);
        printf("\n");
    }
}
void selection_sort(int Array[],int N)//选择排序(升序)
{
    int i,j,k,temp;
    for(i=0;i<N;i++)
    {
        k=i;
        for(j=i+1;j<N;j++)
            if(Array[j]<Array[k])    k=j;
        temp=Array[i];
        Array[i]=Array[k];
        Array[k]=temp;    
    }
}