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 17Example 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
TrueHint: 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) —
loading...
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