算法训练 - 和为T -从一个大小为n的整数集中选取一些元素，使得它们的和等于给定的值T。每个元素限选一次，不能一个都不选。

桃扇骨 2023-07-07 05:52 55阅读 0赞

## 问题描述 ##

从一个大小为n的整数集中选取一些元素，使得它们的和等于给定的值T。每个元素限选一次，不能一个都不选。  
**输入格式**  
　　第一行一个正整数n，表示整数集内元素的个数。  
　　第二行n个整数，用空格隔开。  
　　第三行一个整数T，表示要达到的和。  
**输出格式**  
　　输出有若干行，每行输出一组解，即所选取的数字，按照输入中的顺序排列。  
　　若有多组解，优先输出不包含第n个整数的；若都包含或都不包含，优先输出不包含第n-1个整数的，依次类推。  
　　最后一行输出总方案数。  
例子

**样例输入**  
5  
\-7 -3 -2 5 9  
0  
**样例输出**  
\-3 -2 5  
\-7 -2 9  
2  
**限制**

时间限制：1.0s 内存限制：256.0MB

#include <stdio.h>
    int N, a[22], T, num=0, b[22];
    
    void print(int y)
    { 
        int i;
        for(i=y; i>=0; i--){ 
            printf("%d ", b[i]);
        }   
        printf("\n");
    
    }
    
    void f(int x, int y,int sum)
    { 
        if(x < 0)
    	{ 
            return;
        }
        f(x-1, y, sum);
        b[y] = a[x], sum += a[x];
        if(sum == T)
    	{ 
            num ++;
            print(y);
        }
        f(x-1, y+1, sum);
    }
    
    int main()
    { 
        int i;
        scanf("%d", &N);
        for(i=0; i<N; i++)
            scanf("%d", &a[i]);
        scanf("%d", &T);
        f(N-1, 0, 0);
        printf("%d", num);
        return 0;
    }

*运行示例*

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MjgxODA3_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MjgxODA3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200221141224150.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MjgxODA3,size_16,color_FFFFFF,t_70