欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

从N个数中取M个和为指定值的数

程序员文章站 2022-03-13 12:58:41
...

 一个含有n个元素的数组,找出N个数使其和为target

思路:

     这里使用递归求解

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

bool calNextNumber(int start, int target, int N, vector<int>&ivec, vector<int>arr)
{
	if (target == 0 && N == 0)
		return true;
	if (start + N >= arr.size() || target <= 0)
		return false;
	for (int i = start; i < arr.size(); ++i)
	{
		ivec.push_back(arr[start]);
		if (calNextNumber(i + 1, target - arr[start], N - 1, ivec, arr))
		{
			return true;
		}
		ivec.pop_back();
	}
	return false;
}

vector<vector<int>> cal(vector<int> arr, int target, int N)
{
	int length = arr.size();
	vector<vector<int>> iivec;
	vector<int> ivec;
	for (int i = 0; i < arr.size(); ++i)
	{
		if (calNextNumber(i, target, N, ivec, arr))
			iivec.push_back(ivec);
		ivec.clear();
	}
	return iivec;
}

int main()
{
	vector<int> arr = { 1, 3, 5, 9, 4, 2 };
	sort(arr.begin(), arr.end());
	vector<vector<int>> result = cal(arr, 6, 2);
	for (int i = 0; i < result.size(); ++i)
	{
		for (auto it : result[i])
			cout << it << '\t';
		cout << endl;
	}
    return 0;
}

从N个数中取M个和为指定值的数