LeetCode 018 4 Sum
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note
Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d) The solution set must not contain duplicate quadruplets.
For example, given array S = {1 0 -1 0 -2 2}, and target = 0.
A solution set is:
(-1, 0, 0, 1)
(-2, -1, 1, 2)
(-2, 0, 0, 2)
Diffculty
Medium
Similar Problems
[LeetCode 1] Two Sum E
[LeetCode 15] 3Sum M
[LeetCode 454] 4Sum II M
Analysis
As we have solved 2sum, 3sum, and 3sum closest. It is natural that we derive it to 4sum, and k-sum.
Idea
We derive to a more general problem, k-sum. Using recusive algorithm to reduce k-sum to (k-1)-sum, and then (k-i)-sum, etc...
In k-sum problem, for each element A[i], solve (k-1)-sum in A[i+1], ..., A[n-1] the base problem would be 2-sum. We solve 2-sum using double-pointers algorithm
Key points
Be very careful that we need to skip/remove duplicates.
e.g.
Cases like this that need to be cared :
[1, 1, 1, 2, 3] target = 7
i j
i j(skipped)
We need to get only one solution [1, 1, 2, 3]
k-sum
we need to be clear with the return point. We search k elemennts' sum for a target value, all the way down to search k - 1, ..., until to 0, and we stop the recursion.
Obviously, when k is 0, we stop the process.
when k is 1, we search for only one value, use one indexer
when k is 2, we search for two values, use two indexers
when k is 3, we fix one, then use two indexers
...
Note that when k == 1 and k == 2, one indexer and two indexers algorithms are used seprately, this means we need to deal with them seprately. From k == 3 and above, we recursive call 2-sum algorithm.
Data structure
Use an temp array to store the visited element that in each recursion level. In recursion process, we visit an element, and then go to next recursion level, until we hit recursion stop point. We need to store those ligitmate elements down this road.
Tips
Remember to pop out each element when we unstack the recursion. Also, when we have found a legitimate solution, and we are trying to find more solutions, we need to pop out some elements before we continue, this is the core of back stracking traverse algorithm.
Solutions
- C++ Solution
59 ms
4-sum
class Solution {
public:
vector<vector<int>> fourSum(vector<int> &nums, int target) {
vector<vector<int>> tetrads;
if(nums.size() < 4) return tetrads;
sort(nums.begin(), nums.end());
for(int i = 0; i < (int)nums.size() - 3; ++i){
if(i > 0 && nums[i] == nums[i - 1]) continue;
for(int j = i + 1; j < (int)nums.size() - 2; ++j){
if(j > 1 && i != j - 1 && nums[j] == nums[j - 1]) continue;
twoSum(nums, i, j + 1, target - nums[i] - nums[j], tetrads);
}
}
return tetrads;
}
void twoSum(vector<int> &nums, int start0, int start1, int target, vector<vector<int>> &tetrads){
int i = start1, j = (int)nums.size() - 1;
while(i < j){
int sum = nums[i] + nums[j];
if(sum == target){
tetrads.push_back({nums[start0], nums[start1 - 1], nums[i], nums[j]});
++i; --j;
while(nums[i] == nums[i - 1]) ++i;
while(nums[j] == nums[j + 1]) --j;
}
else if(sum < target) ++i;
else --j;
}
}
};
- k-sum
63 ms
class Solution{
public:
vector<vector<int>> fourSum(vector<int> &num, int target){
vector<vector<int>> allSol;
vector<int> sol;
sort(num.begin(), num.end());
kSum(num, 0, num.size() - 1, target, 4, sol, allSol);
return allSol;
}
void kSum(vector<int> &num, int start, int end, int target, int k, vector<int> &sol, vector<vector<int>> &allSol){
if(k <= 0) return;
if(k == 1){
for(int i = start; i <= end; ++i){
if(num[i] == target){
sol.push_back(num[i]);
allSol.push_back(sol);
sol.pop_back();
return;
}
}
}
if(k == 2){
twoSum(num, start, end, target, sol, allSol);
return;
}
for(int i = start; i <= end - k + 1; ++i){
if(i > start && num[i] == num[i - 1])
continue;
sol.push_back(num[i]);
kSum(num, i + 1, end, target - num[i], k - 1, sol, allSol);
sol.pop_back();
}
}
void twoSum(vector<int> &num, int start, int end, int target, vector<int> &sol, vector<vector<int>> &allSol){
while(start < end){
int sum = num[start] + num[end];
if(sum == target){
sol.push_back(num[start]);
sol.push_back(num[end]);
allSol.push_back(sol);
sol.pop_back();
sol.pop_back();
start++;
end--;
while(num[start] == num[start - 1]) start++;
while(num[end] == num[end + 1]) end--;
}
else if(sum < target) start++;
else end--;
}
}
};
- Golang (4 sum)
22ms
func fourSum(nums []int, target int) [][]int {
all := [][]int{}
if len(nums) < 4 {
return all
}
sort.Ints(nums)
fmt.Println(nums)
for i := 0; i < len(nums)-3; i++ {
if i > 0 && nums[i] == nums[i-1] {
continue
}
for j := i + 1; j < len(nums)-2; j++ {
if j > 1 && i != j-1 && nums[j] == nums[j-1] {
continue
}
twoSum(nums, i, j, target-nums[i]-nums[j], &all)
}
}
return all
}
func twoSum(nums []int, i, j, target int, all *[][]int) {
begin, end := j+1, len(nums)-1
for begin < end {
sum := nums[begin] + nums[end]
if sum == target {
tmp := make([]int, 4)
tmp[0], tmp[1], tmp[2], tmp[3] = nums[i], nums[j], nums[begin], nums[end]
*all = append(*all, tmp)
begin++
end--
for nums[begin] == nums[begin-1] && begin < end {
begin++
}
for nums[end] == nums[end+1] && begin < end {
end--
}
} else if sum < target {
begin++
} else {
end--
}
}
}
- Golang (k sum)
22ms
Note:
Be careful, don't append the []int temp slice, in which push and pop operations are frequently used, to the resulting [][]int slice,
we need deep copy.
func kfourSum(nums []int, target int) [][]int {
all := [][]int{}
if len(nums) < 4 {
return all
}
sort.Ints(nums)
k := 4
sol := []int{}
ksum(nums, &sol, &all, k, 0, len(nums)-1, target)
return all
}
func ksum(nums []int, sol *[]int, all *[][]int, k, begin, end, target int) {
if k == 0 {
return
}
if k == 1 {
for i := begin; i <= end; i++ {
// since nums is sorted in ascending order,
// when nums[i] > target, we no longer need to loop the remaining elements
if nums[i] > target {
return
} else if nums[i] == target {
*sol = append(*sol, nums[i])
*all = append(*all, *sol)
*sol = nil
return
}
}
}
if k == 2 {
two_sum(nums, sol, all, begin, end, target)
return
}
if k > 2 {
for i := begin; i <= end-k+1; i++ {
if i > begin && nums[i] == nums[i-1] {
continue
}
*sol = append(*sol, nums[i])
ksum(nums, sol, all, k-1, i+1, end, target-nums[i])
*sol = (*sol)[0 : len(*sol)-1]
}
}
}
func two_sum(nums []int, sol *[]int, all *[][]int, begin, end, target int) {
for begin < end {
sum := nums[begin] + nums[end]
if sum == target {
*sol = append(*sol, nums[begin], nums[end])
tmp := make([]int, len(*sol))
copy(tmp, *sol) // Note here, critically important!
*all = append(*all, tmp)
// *all = append(*all, append([]int(nil), *sol...))
*sol = (*sol)[0 : len(*sol)-2]
begin++
end--
for nums[begin] == nums[begin-1] && begin < end {
begin++
}
for nums[end] == nums[end+1] && begin < end {
end--
}
} else if sum < target {
begin++
} else {
end--
}
}
}