【学习记录】C语言部分和问题

给定整数a1、a2、…、an，判断是否可以从中选出若干数，使它们的和恰好为k。其中

样例：

输入

   n=4

   a={1,2,4,7}

k=13

输出

  Yes (13=2 + 4 +7)

输入

   n=4

   a={1,2,4,7}

   k=15

输出

  No

程序代码及测试结果：

#include 
bool dfs(int n, int a[], int b[], int k, int sum, int step);

int main() {
	while (1) {
		int n, k;
		scanf("%d", &n);
		int a[n], flag[n] = {0};
		int i, sum = 0, step = 0;
		for (i = 0; i < n; i++) {
			scanf("%d", &a[i]);
		}
		scanf("%d", &k);
		if (dfs(n, a, flag, k, sum, step)) {
			printf("YES(%d=", k);
			for (i = 0; i < n; i++) {
				if (flag[i] == 1)
					printf("%d+", a[i]);
			}
			printf("\b)\n");
		} else
			printf("NO");
	}
}

bool dfs(int n, int a[], int flag[], int k, int sum, int step) {
	if (step == n)
		return sum == k;
	if (dfs(n, a, flag, k, sum + a[step], step + 1)) {
		flag[step] = 1;
		return true;
	}
	if (dfs(n, a, flag, k, sum, step + 1)) {
		flag[step] = 0;
		return true;
	}
	return false;
}

2022/5/15