部分和问题 代码(C)

本文地址: http://blog.csdn.net/caroline_wendy

题目: 给定整数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\n");
	else printf("No\n");
}


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