首页 / 软件开发 / 数据结构与算法 / 部分和问题算法 代码（C）

部分和问题算法 代码（C）2015-10-28题目: 给定整数a1, a2, ..., an, 判断是否可以从中选出若干数, 使它们的和恰好为k.

解法很多, 最简单的解法是使用深度优先搜索, 时间复杂度O（2^n）, 不是最优解法.

代码:

/** main.cpp**Created on: 2014.7.13* *Author: Spike*//*eclipse cdt, gcc 4.8.1*/#include <stdio.h>bool dfs （int i, int sum, int* a, int n, int k） {if （i==n） return sum == k;if（dfs（i+1, sum, a, n, k）） return true;if（dfs（i+1, sum+a[i], a, n, k）） return true;return false;}void solve（int* a, int n, int k） {if （dfs（0,0,a,n,k）） printf（"Yes
"）;else printf（"No
"）;}int main（void）{const int MAX_N = 20;int a[MAX_N] = {1, 2, 4, 7};int n = 4, k = 13; //k位需要找到的数字solve（a, n, k）;return 0;}

输出:

Yes

作者：csdn博客 Mystra