数组部分和的问题：假设有一个数组a[N], 能不能从数组a中任选M个元素(M <= N)，使得其和为K。

Question

M，N，K都是未知数，貌似不能用枚举法，怎样编写程序（C语言）输出如下测试实例：
输入 1 2 3 4 5 7
K=8
输出
1 3 4
1 7
1 2 5

Answer 1

next_permutation全排列问题

#include <iostream>
#include <algorithm>
using namespace std;
#pragma warning(disable:4996)
int main() {
    int m, n, k;
    scanf("%d %d", &n,&k);
    int *arrs = new int[n];
    for (int i = 0; i < n; i++) {
        arrs[i] = i + 1;
    }
    do {
        for (int i = 0; i < n; i++) {
            printf("%d ",arrs[i]);
        }
        printf("\n");
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += arrs[i];
            if (sum == k) {
                printf("前几项能凑成%d\n",k);
                break;
            }
        }
    } while (next_permutation(arrs, arrs + n));
    printf("前几项能凑成k");
}

用例
5 4
1 2 3 4 5
1 2 3 5 4
1 2 4 3 5
1 2 4 5 3
1 2 5 3 4
1 2 5 4 3
1 3 2 4 5
前几项能凑成4
1 3 2 5 4
前几项能凑成4
1 3 4 2 5
前几项能凑成4
1 3 4 5 2
前几项能凑成4
1 3 5 2 4
前几项能凑成4
1 3 5 4 2
前几项能凑成4
1 4 2 3 5
1 4 2 5 3
1 4 3 2 5
1 4 3 5 2
1 4 5 2 3
1 4 5 3 2
1 5 2 3 4
1 5 2 4 3
1 5 3 2 4
1 5 3 4 2
1 5 4 2 3
1 5 4 3 2
2 1 3 4 5
2 1 3 5 4
2 1 4 3 5
2 1 4 5 3
2 1 5 3 4
2 1 5 4 3
2 3 1 4 5
2 3 1 5 4
2 3 4 1 5
2 3 4 5 1
2 3 5 1 4
2 3 5 4 1
2 4 1 3 5
2 4 1 5 3
2 4 3 1 5
2 4 3 5 1
2 4 5 1 3
2 4 5 3 1
2 5 1 3 4
2 5 1 4 3
2 5 3 1 4
2 5 3 4 1
2 5 4 1 3
2 5 4 3 1
3 1 2 4 5
前几项能凑成4
3 1 2 5 4
前几项能凑成4
3 1 4 2 5
前几项能凑成4
3 1 4 5 2
前几项能凑成4
3 1 5 2 4
前几项能凑成4
3 1 5 4 2
前几项能凑成4
3 2 1 4 5
3 2 1 5 4
3 2 4 1 5
3 2 4 5 1
3 2 5 1 4
3 2 5 4 1
3 4 1 2 5
3 4 1 5 2
3 4 2 1 5
3 4 2 5 1
3 4 5 1 2
3 4 5 2 1
3 5 1 2 4
3 5 1 4 2
3 5 2 1 4
3 5 2 4 1
3 5 4 1 2
3 5 4 2 1
4 1 2 3 5
前几项能凑成4
4 1 2 5 3
前几项能凑成4
4 1 3 2 5
前几项能凑成4
4 1 3 5 2
前几项能凑成4
4 1 5 2 3
前几项能凑成4
4 1 5 3 2
前几项能凑成4
4 2 1 3 5
前几项能凑成4
4 2 1 5 3
前几项能凑成4
4 2 3 1 5
前几项能凑成4
4 2 3 5 1
前几项能凑成4
4 2 5 1 3
前几项能凑成4
4 2 5 3 1
前几项能凑成4
4 3 1 2 5
前几项能凑成4
4 3 1 5 2
前几项能凑成4
4 3 2 1 5
前几项能凑成4
4 3 2 5 1
前几项能凑成4
4 3 5 1 2
前几项能凑成4
4 3 5 2 1
前几项能凑成4
4 5 1 2 3
前几项能凑成4
4 5 1 3 2
前几项能凑成4
4 5 2 1 3
前几项能凑成4
4 5 2 3 1
前几项能凑成4
4 5 3 1 2
前几项能凑成4
4 5 3 2 1
前几项能凑成4
5 1 2 3 4
5 1 2 4 3
5 1 3 2 4
5 1 3 4 2
5 1 4 2 3
5 1 4 3 2
5 2 1 3 4
5 2 1 4 3
5 2 3 1 4
5 2 3 4 1
5 2 4 1 3
5 2 4 3 1
5 3 1 2 4
5 3 1 4 2
5 3 2 1 4
5 3 2 4 1
5 3 4 1 2
5 3 4 2 1
5 4 1 2 3
5 4 1 3 2
5 4 2 1 3
5 4 2 3 1
5 4 3 1 2
5 4 3 2 1