数组中任意几个元素的和是否等于m(递归)

1.问题描述


已知一个一维数组,又已知一个整数m。如果能使数组a中几个元素之和等于m,则输出Yes,否则输出No。

样例输入:3

                   3 1 6

                   6

样例输出:Yes


2.算法分析


其实这道题目意思就是,假定数组为nums,就是让我们判断能否从数组nums取任意数使其和为m

对于nums中任意元素nums[n]只有取或者不取两种情况:

1.取nums[n]

问题就要转化为:对于一个确定的数组nums[1...n-1]和一个确定的数m-nums[n],判断能否使数组nums[1....n-1]中任意几个元素的和为m-nums[n]即可。

2.不取nums[n]

此时问题转化为:对于一个已确定的数组nums[1..n]和一个确定的数m,判断能否使数组nums[1...n-1]中任意几个元素之和为m。


3.源代码


#include
using namespace std;

int nums[101];
int n;	//数组元素个数
int m;	//数组中存在n个元素和为m
bool flag;

void sum(int n,int m)   //求数组中是否存在一些元素和等于m
{
	if(nums[n] == m) flag = true;  //假设数组的最后一个元素等于和m,将flag变量置为true
	else if(n == 1) return;    //搜索完了整个数组返回
	else
	{
		sum(n-1,m-nums[n]);   //说明取了nums[n]元素
		sum(n-1,m);	//说明没有取nums[n] 
	} 
} 

int main()
{
	cin>>n;
	for(int i =1;i<=n;i++)
	{
		cin>>nums[i]; 
	}
	cin>>m;
	flag = false; //初始时,将flag置为false,当找到某些元素和为m的时候在sum函数中flag的值将改变
	sum(n,m);
	if(flag)
	cout<<"Yes"<

 

你可能感兴趣的