从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;
}
上一篇: LeetCode—分治