Teaching Kids Programming – Sum of Four Numbers using Depth First Search Algorithm


Teaching Kids Programming: Videos on Data Structures and Algorithms

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

Hint: Find 2 elements sum up to k

Depth First Search Algorithm to Find Sum of Four

We can perform a Depth First Search Algorithm on this – keeping tracking of the remaining sum to pick and how many numbers left to pick. If we have picked four numbers already, we can directly return true if the remaining sum is zero.

If we have run out of the numbers, we return false. Otherwise, for current number, we can choose pick or not pick.

1
2
3
4
5
6
7
8
9
class Solution:
    def solve(self, nums, k):
        def dfs(left, count, s):
            if count == 4:
                return s == 0
            if left >= len(nums):
                return False
            return dfs(left + 1, count, s) or dfs(left + 1, count + 1, s - nums[left])
        return dfs(0, 0, k)
class Solution:
    def solve(self, nums, k):
        def dfs(left, count, s):
            if count == 4:
                return s == 0
            if left >= len(nums):
                return False
            return dfs(left + 1, count, s) or dfs(left + 1, count + 1, s - nums[left])
        return dfs(0, 0, k)

The time complexity is O(N^4). The space complexity is O(N) as we are using Recursion.

See also: Recursive and Two Pointer Algorithms to Determine Four Sum

Bruteforce Algorithm to Check Sum of Four

We can perform a bruteforce algorithm to try every possible unique pairs of four and see if their sum is target:

1
2
3
4
5
6
7
8
9
10
class Solution:
    def solve(self, nums, T):
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    for u in range(k + 1, n):
                        if nums[i] + nums[j] + nums[k] + nums[u] == T:
                            return True
        return False
class Solution:
    def solve(self, nums, T):
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    for u in range(k + 1, n):
                        if nums[i] + nums[j] + nums[k] + nums[u] == T:
                            return True
        return False

Four Sum can be solved via Two Pointer Algorithm: Teaching Kids Programming – Two Pointer Algorithm to Solve Four Sum Problem

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
514 words
Last Post: An Example Email to Negotiate Your Package (Salary) - Counter Offer Template
Next Post: Teaching Kids Programming - Dynamic Programming or Greedy Algorithm to Compute the Min Change

The Permanent URL is: Teaching Kids Programming – Sum of Four Numbers using Depth First Search Algorithm

Leave a Reply