20170727 - 4Sum

class Solution {
public:
std::vector <std::vector<int>> ThreeSum(std::vector<int>& nums, int target, int source)
{
	int l, r,sum;
	std::vector<int> temp;
	std::vector <std::vector<int>> result;
	sort(nums.begin(), nums.end());
	for (int i = 0; i < nums.size(); i++)
	{
		l = i + 1;
		r = nums.size() - 1;
		while (l < r)
		{
			sum = nums[i] + nums[l] + nums[r];
			if (sum == target)
			{
				temp.clear();
				temp.push_back(source);
				temp.push_back(nums[i]);
				temp.push_back(nums[l]);
				temp.push_back(nums[r]);
				while (l <= r && nums[l] == temp[2]) l++;
				while (l <= r && nums[r] == temp[3]) r--;
				sort(temp.begin(), temp.end());
				result.push_back(temp);
			}
			else if (sum > target) r--;
			else if (sum < target) l++;
		}
	}

	return result;
}

std::vector<std::vector<int>> fourSum(std::vector<int>& nums, int target) {

	std::vector<int> temp;
	std::vector<std::vector<int>> childresult;
	std::vector<std::vector<int>> result;
	for (std::vector<int>::iterator i = nums.begin();i<nums.end();i++)
	{
		temp.clear();
		temp.insert(temp.begin(), i+1, nums.end());
		childresult = ThreeSum(temp, target - *i, *i);
		result.insert(result.begin(), childresult.begin(),childresult.end());
	}

	sort(result.begin(), result.end());
	result.erase(unique(result.begin(), result.end()), result.end());
	return result;
}

};