編程算法 - 部分和問題 代碼(C)

編程算法 - 部分和問題 代碼(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