子序列和 c++ dfs

题目描述

给定整数a1、a2、…an（1<=a1…an<=1000）。推断能否从中选出若干数，使它们的和恰好为k。

输入格式:

首先，n和k（1<=n<=25），n表示数的个数。k表示数的和。接着一行n个数。

输出格式:

假设和恰好能够为k，输出“YES”，并按输入顺序依次输出是由哪几个数的和组成（若有多种可能情况，输出第一个满足条件的结果，请参考第二个样例）。否则“NO”。

输入样例:

4 13
1 2 4 7
12 10
6 2 4 7 5 3 2 1 6 9 10 2
12 58
6 2 4 7 5 3 2 1 6 9 10 2

输出样例:

YES
2 4 7
YES
6 2 2
NO

解题代码

定义变量

const int maxLength = 30;

int n, k;
//判断是否找到答案
bool flag = false;
//记录当前的数组和答案数组
vector<int>temp, answer;
//题目输入的数组
vector<int>nums(maxLength);
//表示对应下标的数组元素是否被访问，防止重复填入数组
vector<bool>vis(maxLength, false);

数据初始化

//防止多组数据间互相干扰，初始化数据
flag = false;
fill(vis.begin(), vis.begin() + maxLength, false);

数据读入

while (cin >> n >> k)
{
	for (int i = 0; i < n; i++)
	{
		cin >> nums[i];
	}
}

递归实现

//i表示上一个填入的数为nums[i]，sum为当前temp数组中元素的和
//再次填数时从i开始，防止重复填入填过的数组导致超时
void dfs(int i, int sum)
{
    //如果找到答案或当前数组和大于k，都不需要继续递归填数，return返回
	if (flag || sum > k) return;
	//找到答案
	if (sum == k)
	{
		flag = true;
		answer = temp;
		return;
	}
//遍历数组，尝试nums[j]填入temp数组，更新sum的值为sum+nums[j]
//填入nums[s]的递归结束，再尝试取消填入nums[j]
	for (int j = i; j < n; j++)
	{
		if (!vis[j])
		{
			vis[j] = true;
			temp.push_back(nums[j]);
			dfs(j, sum + nums[j]);
			vis[j] = false;
			temp.pop_back();
		}
	}
}

输出结果

void showAnswer()
{
	if (flag)
	{
		cout << "YES" << endl;

		cout << answer[0];
		for (int i = 1; i < answer.size(); i++)
		{
			cout << ' ' << answer[i];
		}
		cout << endl;
	}
	else
	{
		cout << "NO" << endl;
	}
}

整体代码

#include <iostream>
#include <vector>

using namespace std;

const int maxLength = 30;

int n, k;
bool flag = false;
vector<int>temp, answer;
vector<int>nums(maxLength);
vector<bool>vis(maxLength, false);

void dfs(int i, int sum)
{
	if (flag || sum > k) return;

	if (sum == k)
	{
		flag = true;
		answer = temp;
		return;
	}
	
	for (int j = i; j < n; j++)
	{
		if (!vis[j])
		{
			vis[j] = true;
			temp.push_back(nums[j]);
			dfs(j, sum + nums[j]);
			vis[j] = false;
			temp.pop_back();
		}
	}
}

void showAnswer()
{
	if (flag)
	{
		cout << "YES" << endl;

		cout << answer[0];
		for (int i = 1; i < answer.size(); i++)
		{
			cout << ' ' << answer[i];
		}
		cout << endl;
	}
	else
	{
		cout << "NO" << endl;
	}
}

void solve()
{
	flag = false;
	fill(vis.begin(), vis.begin() + maxLength, false);

	for (int i = 0; i < n; i++)
	{
		cin >> nums[i];
	}

	dfs(0, 0);
	
	showAnswer();
}

int main()
{
	while (cin >> n >> k)
	{
		solve();
	}

	return 0;
}