Closest Subsequence Sum LeetCode solution in Python

1
class Solution:
2
    def minAbsDifference(self, nums: List[int], goal: int) -> int:
3

4
        # When goal 0 we can just choose no elements
5
        if goal == 0:
6
            return 0
7

8
        n = len(nums)
9
        mid = n // 2
10
        # Split the list in 2 parts and then find all possible subset sums
11
        # T = O(2^n/2) to build all subset sums
12
        leftList = nums[:mid]
13
        leftSums = []
14
        rightList = nums[mid:]
15
        rightSums = []
16

17
        # T = O(2^n/2) to build all subset sums (we only consider half list)
18
        def buildSubsetSums(usedNums, numsToChooseFrom, ind, storeIn):
19
            if ind == len(numsToChooseFrom):
20
                # We also keep elements with sum 0 to deal with cases like this where we don't select nums
21
                # List: [1,2,3], Target: -7 (choosing no elements will give a sum close to goal)
22
                # We can also have cases where we want to take only 1 element from the list
23
                # so sum 0 for left and right list needs to be an option
24
                storeIn.append(sum(usedNums))
25
                return
26

27
            usedNums.append(numsToChooseFrom[ind])
28
            buildSubsetSums(usedNums, numsToChooseFrom, ind + 1, storeIn)
29
            usedNums.pop()
30
            buildSubsetSums(usedNums, numsToChooseFrom, ind + 1, storeIn)
31

32
        buildSubsetSums([], leftList, 0, leftSums)
33
        buildSubsetSums([], rightList, 0, rightSums)
34
        # 2^n/2 log(2^n/2) = n/2 * 2^n/2 time to sort
35
        rightSums.sort()
36

37
        diff = float("inf")
38

39
        # Loop runs 2^n/2 times and inside binary search tale n/2 time
40
        # So total time is n/2 * 2^n/2
41
        for leftSum in leftSums:
42
            complement = goal - leftSum
43
            # Bisect left takes log(2^n/2) = n/2 search time
44
            idx = bisect.bisect_left(rightSums, complement)
45

46
            for i in [idx - 1, idx, idx + 1]:
47
                if 0 <= i < len(rightSums):
48
                    finalSum = leftSum + rightSums[i]
49
                    diff = min(diff, abs(goal - finalSum))
50

51
        # Over all time complexity is - n/2 * 2^n/2
52
        # 1. Making subset sums will take - 2^n/2
53
        # 2. Sorting right list takes - 2^n/2 * n/2
54
        # 3. Iterating one list and finding closest complement in other
55
        # takes n/2 * 2^n/2
56
        # Space will be O(n/2) for the list and call stack for building subset
57
        return diff