LinkedIn | Onsite | Split an array into K equal sum subsets
Anonymous User
2946
LinkedInOnsiteInterview

Hello,

I received the below question during onsite some days ago. Actually I could not resolve it within time and submitted uncompleted solution using backtracking approach. I solved it after the onsite. To be honest with you I don't expect I can pass the onsite, but I wanna discuss it and get various approachs from you guys.

The problem was that I need to return True/False if possible to split an integer array into K subarrays whose sums are equal and non-empty.
For example,
Input: [1, 2, 4, 3, 5, 3], K: 3
We can split the input into 3 sub-arrays and they has same sum == 6 like [1, 5], [2, 4], [3, 3]. True

Input: [4, 2, 3, 1], K: 2
We can split the input into 2 sub-arrays and they has same sum == 5 like [4, 1], [2, 3]. True

Input: [3, 3, 3, 3, 4], K: 2
There is no 2 subarray pair in which each one has same sum.
[3, 3, 3, 3] [4] (X) [3, 3, 3] [3,4] (X) [3, 3] [3, 3,4] (X) [3] [3, 3, 3,4] (X) False

My solution is like this using backtracking:

#Time complexity: K ^ N: Any num can be placed into K-th bucket
#Space complexity: N (recursive depth and visited array) 

NOT_YET_ASSIGNED = -1

def subArray(input, k):
    total = sum(input)
    if total % k != 0:
        return False

    memo = set()
    expected = total // k
    length = len(input)
    assigned = [NOT_YET_ASSIGNED for i in range(length)]
    def backtracking(bucketIndex, curSum, assigned):
        nonlocal length, expected, memo
        if bucketIndex == k:
            return True

        for i in range(length):
            num = input[i]
            if num + curSum <= expected \
                and not (num, bucketIndex, curSum) in memo \
                and assigned[i] == NOT_YET_ASSIGNED:
                # Assign num to current bucket
                assigned[i] = bucketIndex
                if backtracking(bucketIndex + 1 if num + curSum == expected else bucketIndex, 
                    0 if num + curSum == expected else num + curSum, 
                    assigned):
                    return True
                
                assigned[i] = NOT_YET_ASSIGNED
                memo.add((num, bucketIndex, curSum))
        return False

    return backtracking(0, 0, assigned)

print(subArray([4, 3, 2, 2, 1], 2)) # True
print(subArray([4, 2, 3, 1], 2)) # True
print(subArray([1, 2, 4, 3, 5, 3], 3)) # True
print(subArray([3, 3, 3, 3, 4], 3)) # False

I will welcome various approaches.

Comments (2)