1338. Reduce Array Size to The Half

https://leetcode.com/problems/reduce-array-size-to-the-half/

Python

Backtracking (Timelimit Exceed)

• Time: O(N!)
• Space: O(M) # M is the count of non-duplicated num in the arr

from collections import Counter
from math import inf


class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        counts = Counter(arr)
        half = len(arr) >> 1

        nums = counts.keys()

        def backtrack(path: set):
            if sum([counts[num] for num in nums if num not in path]) <= half:
                return len(path)

            minium = inf
            for num in nums:
                if num in path:
                    continue
                path.add(num)
                minium = min(minium, backtrack(path))
                path.remove(num)

            return minium

        return backtrack(set())