Recursion and Two Pointer Algorithms to Determine Four Sum

Given a list of integers nums and an integer k, return whether there are four distinct elements in the list that add up to k.

Constraints
n ≤ 100 where n is length of nums.
Example 1
Input
nums = [10, 3, 5, 9, 4, 0]
k = 17
Output
true
Explanation
We can use [10, 3, 4, 0] to get 17

Example 2
Input
nums = [2]
k = 8
Output
false
Explanation
There’s no 4 numbers that sum up to 2.

Example 3
Input
nums = [2, 2, 2, 2]
k = 8
Output
true

This is the similar question as 4Sum – Find Unique Quadruplets that Sum to Target using O(N^3) Four Pointers Algorithm except that we just need to figure out if there is four sum without needing to print them all.

Two Pointer Algorithm to Solve Four Sum

We can reduce the problem into a Two Sum Problem. In order to do this, we need to sort the array, then we can have a O(N^2) pair to try the first two distinct numbers, then, we can use two pointer algorithm for the rest of range to look for the speific sum. The time complexity is O(N^3).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

bool fourSum(vector<int>& nums, int k) {
    if (nums.empty()) return false;        
    sort(begin(nums), end(nums));
    int n = nums.size();
    for (int i = 0; i < n; ++ i) {
        if ((i > 0) && (nums[i] == nums[i - 1])) continue;
        for (int j = i + 1; j < n; ++ j) {
            if ((j > i + 1) && (nums[j] == nums[j - 1])) continue;
            int kk = j + 1;
            int uu = n - 1;
            while (kk < uu) {
                int s = nums[i] + nums[j] + nums[kk] + nums[uu];
                if (s == k) {
                    return true;
                } else if (s > k) {
                    uu --;
                } else {
                    kk ++;
                }
            }
        }
    }
    return false;
}

bool fourSum(vector<int>& nums, int k) {
    if (nums.empty()) return false;        
    sort(begin(nums), end(nums));
    int n = nums.size();
    for (int i = 0; i < n; ++ i) {
        if ((i > 0) && (nums[i] == nums[i - 1])) continue;
        for (int j = i + 1; j < n; ++ j) {
            if ((j > i + 1) && (nums[j] == nums[j - 1])) continue;
            int kk = j + 1;
            int uu = n - 1;
            while (kk < uu) {
                int s = nums[i] + nums[j] + nums[kk] + nums[uu];
                if (s == k) {
                    return true;
                } else if (s > k) {
                    uu --;
                } else {
                    kk ++;
                }
            }
        }
    }
    return false;
}

Recursive Algorithm to Solve Four Sum

Alternatively, we can perform a Recursive search with O(N^4) time complexity to look for all possible pairs of Four Sum:

1
2
3
4
5
6
7
8
9
10
11

bool fourSum(vector<int>& nums, int k) {
    function<bool(int, int, int)> dfs = [&](int left, int count, int sum) {
        if (count == 4) {
            return sum == 0;
        }
        if (left >= nums.size()) return false;
        return dfs(left + 1, count, sum) || 
               dfs(left + 1, count + 1, sum - nums[left]);
    };
    return dfs(0, 0, k);
}

bool fourSum(vector<int>& nums, int k) {
    function<bool(int, int, int)> dfs = [&](int left, int count, int sum) {
        if (count == 4) {
            return sum == 0;
        }
        if (left >= nums.size()) return false;
        return dfs(left + 1, count, sum) || 
               dfs(left + 1, count + 1, sum - nums[left]);
    };
    return dfs(0, 0, k);
}

See the implemention of Python of Four Sum: Teaching Kids Programming – Sum of Four Numbers using Depth First Search Algorithm

Two Sum Variation Problems

• Teaching Kids Programming - Two Sum in Binary Search Tree via Inorder and Two Pointer Algorithm
• Teaching Kids Programming - Count Pairs Whose Sum is Less than Target (Two Pointer Algorithm)
• Teaching Kids Programming - Sum of Two Numbers Less Than Target using Two Pointer Algorithm
• Teaching Kids Programming - Two Pointer Algorithm to Solve Four Sum Problem
• Teaching Kids Programming - Recursive Algorithm to Find the Sum of Two Numbers in BSTs
• Two Pointer Algorithm to Count the Sum of Three Numbers Less than Target
• Recursive and Two Pointer Algorithms to Determine Four Sum
• Algorithms to Check Sum of Two Numbers in Binary Search Trees
• Teaching Kids Programming - 3 Different Approaches to Solve Two-Sum Problem
• How to Design a Two-Sum Data Structure?
• How to Find the Closest Sum of Three in an Array using Two Pointer Algorithm? (3Sum Closest)
• Teaching Kids Programming - Three Sum Algorithm
• Teaching Kids Programming – Two Sum Algorithm when Input Array is Sorted
• Teaching Kids Programming – Two Sum Algorithm
• Two Pointer Algorithm to Find Maximum Two Sum Less Than K
• The Two Sum Algorithm using HashMap in C++/Java

–EOF (The Ultimate Computing & Technology Blog) —