K-Sum

K-Sum

December 20, 2023
medium
backtracking

Problem #

Given an integer k and a list of integers, find if there exists k numbers in the list that add up to 0. Return true if such a set is possible, false otherwise.

Solution # 

def can_find_k_sum(nums, k, start, target):
    # If k is 0, then we have found a combination that sums up to the target
    if k == 0:
        return target == 0

    # If we have run out of numbers to add, return False
    if start == len(nums):
        return False

    # Include the current number and check if a combination is possible
    if can_find_k_sum(nums, k - 1, start + 1, target - nums[start]):
        return True

    # Exclude the current number and check if a combination is possible
    return can_find_k_sum(nums, k, start + 1, target)

def can_partition_k(nums, k):
    # Edge case: if we don't have enough numbers
    if len(nums) < k:
        return False

    return can_find_k_sum(nums, k, 0, 0)

# Test the function with an example
print(can_partition_k([-5, -3, -2, -1, 0, 1, 2, 3, 4, 5], 3))  # Should return True as there are combinations that sum up to 0
  • can_find_k_sum is a helper function that uses recursion and backtracking to find if there exists a combination of k numbers that sum up to the target (in this case, 0).
  • The function can_partition_k calls this helper function, starting with the entire array, k, and a target sum of 0.

This solution efficiently checks all possible combinations of k numbers in the list to see if any of them sum up to 0.