编程算法 - 部分和问题 代码(C)

Tags: c语言

部分和问题 代码(C)

 

题目: 给定整数a1, a2, ..., an, 判断是否可以从中选出若干数, 使它们的和恰好为k.

 

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

 

代码:

 

/*
 * main.cpp
 *
 *  Created on: 2014.7.13
 *      Author: Spike
 */

/*eclipse cdt, gcc 4.8.1*/

#include 

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


 

 

 

 

 

 

 

本文链接:http://www.4byte.cn/learning/53380.html