# k number sum problem

Title: given n integers, k and target, find k numbers in these n numbers, make the sum of k numbers equal to target, and output all possible solutions.

Solution: if k is an even number, sort n integers first, and then find the sum of each k/2 number (for example, find the sum of each two numbers in the 4sum problem) in the HashMap (the set of array subscripts of key: two numbers and value: sum). Traverse the HashMap. If target-x exists for the current element X and is also in the HashMap, pair the subscripts set corresponding to X and target-x to produce A solution needs to be de duplicated in the process (at present, we only want to sort the paired array containing k subscripts, and then use set to de duplicate).

If K is an odd number, sort n integers first, and then find the sum of every k/2 numbers and store it in HashMap. Traverse the array. If there is a pair of X and target-a-x in the current element a and HashMap, pair the subscript set corresponding to X and target-a-x to generate a solution, which needs to be de duplicated in the process.

```class Solution {
public:
void mergeTwoSum(vector<int>& nums, set<vector<int>>& res, vector<vector<int>> list1, vector<vector<int>> list2) {
for (int i = 0; i < list1.size(); i++)
{
for (int j = 0; j < list2.size(); j++)
{
if (list1[i] == list2[j] || list1[i] == list2[j])
continue;
if (list1[i] == list2[j] || list1[i] == list2[j])
continue;
vector<int> temp;
temp.push_back(nums[list1[i]]);
temp.push_back(nums[list1[i]]);
temp.push_back(nums[list2[j]]);
temp.push_back(nums[list2[j]]);
sort(temp.begin(), temp.end());
res.insert(temp);
}
}
}

vector<vector<int>> fourSum(vector<int>& nums, int target) {
int n = nums.size();
vector<vector<int>> res;
set<vector<int>> res_set;
map<int, vector<vector<int>>> twoSum;
sort(nums.begin(), nums.end());
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
vector<int> temp;
temp.push_back(i);
temp.push_back(j);
twoSum[nums[i] + nums[j]].push_back(temp);
}
}
map<int, vector<vector<int>>>::iterator it;
for (it = twoSum.begin(); it != twoSum.end(); it++)
{
int a = it->first;
int b = target - a;
if (a > b)
break;
if (twoSum.find(b) != twoSum.end())
mergeTwoSum(nums, res_set, it->second, twoSum[b]);
}
res.assign(res_set.begin(), res_set.end());
return res;
}
};```

Tags: Erlang

Posted on Sat, 02 Nov 2019 04:33:32 -0700 by hijack