2638. Count the Number of K-Free Subsets

• compute into subset each with element of difference k

class Solution:
    def countTheNumOfKFreeSubsets(self, nums: List[int], k: int) -> int:
        
        def select(start, diff, size, s):
            res = []

            for y in range(start, start + diff * (size - 1), diff):
                if y in s and (not res or y - diff == res[-1]):
                    res.append(y)
                    s.remove(y)
                else:
                    break
            
            return res, s

        
        s = set(nums)
        aux = []

        while s:
            temp, s = select(min(s), k, len(s) + 1, s)
            aux.append(temp)

        dp = {}
        dp[1] = 2
        dp[2] = 3

		# number of combination using the first n element, hence for i_th element, it can either not include itself (i - 1) or include it self (i - 2)
        
        def computeCombinations(number):
            if number in dp:
                return dp[number]
            for i in range(3, number + 1):
                dp[i] = dp[i - 1] + dp[i - 2]
            return dp[number] 


        res = 1

        for x in aux:
            res *= computeCombinations(len(x))

        return res