How hard is LeetCode 1755. Closest Subsequence Sum?

LeetCode 1755. Closest Subsequence Sum is rated Hard on LeetCode.

What is the time complexity of LeetCode 1755. Closest Subsequence Sum?

The Python solution on this page runs in O(n) (after optional sort O(n log n)).

What is the space complexity of LeetCode 1755. Closest Subsequence Sum?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 1755. Closest Subsequence Sum cover?

LeetCode 1755. Closest Subsequence Sum is tagged Bit Manipulation, Array, Two Pointers, Dynamic Programming, Bitmask and Sorting on LeetCode.

Closest Subsequence Sum — LeetCode 1755 Python Solution

HardBit ManipulationArrayTwo PointersDynamic ProgrammingBitmaskSorting

Problem: #1755
Pattern: Bit Manipulation
Reading time: 6 min
Source: leetcode.com

The problem

You are given an integer array nums and an integer goal. You want to choose a subsequence of nums such that the sum of its elements is the closest possible to goal.

Example

Input: nums = [5,-7,3,5], goal = 6
Output: 0
Explanation: Choose the whole array as a subsequence, with a sum of 6.

Python solution

Python

class Solution:
    def minAbsDifference(self, nums: List[int], goal: int) -> int:
        n = len(nums)
        left = set()
        right = set()

        self.getSubSeqSum(0, 0, nums[: n // 2], left)
        self.getSubSeqSum(0, 0, nums[n // 2 :], right)

        result = inf
        right = sorted(right)
        rl = len(right)

        for l in left:
            remaining = goal - l
            idx = bisect_left(right, remaining)

            if idx < rl:
                result = min(result, abs(remaining - right[idx]))

            if idx > 0:
                result = min(result, abs(remaining - right[idx - 1]))

        return result

    def getSubSeqSum(self, i: int, curr: int, arr: List[int], result: Set[int]):
        if i == len(arr):
            result.add(curr)
            return

        self.getSubSeqSum(i + 1, curr, arr, result)
        self.getSubSeqSum(i + 1, curr + arr[i], arr, result)

Complexity

Measure	Complexity
Time	O(n) (after optional sort O(n log n))
Space	O(1) auxiliary

Pattern: Bit Manipulation

Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 1755. Closest Subsequence Sum is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Bit Manipulation and Bitmask.

The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1755. Closest Subsequence Sum?: LeetCode 1755. Closest Subsequence Sum is rated Hard on LeetCode.
What is the time complexity of LeetCode 1755. Closest Subsequence Sum?: The Python solution on this page runs in O(n) (after optional sort O(n log n)).
What is the space complexity of LeetCode 1755. Closest Subsequence Sum?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 1755. Closest Subsequence Sum cover?: LeetCode 1755. Closest Subsequence Sum is tagged Bit Manipulation, Array, Two Pointers, Dynamic Programming, Bitmask and Sorting on LeetCode.