Four Number Sum

• Time : O(2^4 * n)
• Space : O(2^4 * n)

#include <vector>
using namespace std;

vector<vector<int>> fourNumberSum(vector<int> array, int targetSum) {
  unordered_map<int, vector<vector<int>>> mp[3];
	vector<vector<int>> res;
	for(auto& a : array) {
		for(auto comb : mp[2][targetSum - a]) {
			comb.push_back(a);
			res.push_back(comb);
		}
		
		for(auto& [sum, combs] : mp[1]) {
			for(auto comb : combs) {
				comb.push_back(a);
				mp[2][sum + a].push_back(comb);
			}
		}
		
		for(auto& [sum, combs] : mp[0]) {
			for(auto comb : combs) {
				comb.push_back(a);
				mp[1][sum + a].push_back(comb);
			}
		}
		
		mp[0][a].push_back({a});
	}
  return res;
}

• Time : O(n^2)
• Space : O(n^2)

#include <vector>
using namespace std;

vector<vector<int>> fourNumberSum(vector<int> array, int targetSum) {
  unordered_map<int, vector<vector<int>>> twoSums;
	vector<vector<int>> res;
	int n = array.size();
	
	for(int i = 1; i < n; i++) {
		for(int j = i + 1; j < n; j++) {
			int sum = array[i] + array[j];
			int find = targetSum - sum;
			if(twoSums.count(find)) {
				for(auto sums : twoSums[find]) {
					sums.push_back(array[i]);
					sums.push_back(array[j]);
					res.push_back(sums);
				}
			}
		}
		for(int j = 0; j < i; j++) {
			int sum = array[i] + array[j];
			twoSums[sum].push_back({array[i], array[j]});
		}
	}
	
  return res;
}