2369. Check if There is a Valid Partition For The Array

Link

Backtrack

class Solution:
    def validPartition(self, nums: List[int]) -> bool:

        n = len(nums)

        @cache
        def backtrack(i):
            if i == n:
                return True

            res = []

            if i + 1 < n:
                res.append(False if nums[i] != nums[i+1] else backtrack(i+2))
            
            if i + 2 < n:
                res.append(False if nums[i] != nums[i+1] or nums[i+1] != nums[i+2]  else backtrack(i+3))
                res.append(False if nums[i] != nums[i+1] - 1 or nums[i+1] != nums[i+2] - 1 else backtrack(i+3))

            return any(res)

        return backtrack(0)

DP

class Solution:
    def validPartition(self, nums: List[int]) -> bool:

        n = len(nums)

        nums = [0] + nums

        dp = [0] * (n+1)
        dp[0] = 1

        for i in range(1, n + 1):
            if i - 2 >= 0 and nums[i] == nums[i-1]:
                dp[i] = dp[i-2]
            if i - 3 >= 0 and (nums[i] == nums[i-1] == nums[i-2]):
                dp[i] = dp[i] or dp[i-3]
            if i - 3 >= 0 and nums[i] == nums[i-1] + 1 == nums[i-2] + 2:
                dp[i] = dp[i] or dp[i-3]

        return True if dp[-1] == 1 else False