Backtracking with Pruning — அடிப்படை

கத்தரிப்பு — சாத்தியமற்ற கிளைகள்; எஞ்சிய திறன்; monotonicity.

உண்மை உலகில் இது ஏன் முக்கியம்?

புதிர்; கட்டுப்பாட்டு தீர்வி; நேர்காணல் — நிலை, சுயமுறை, மீளமைப்பு.

மையக் கருத்து (மாணவர்களுக்கான விளக்கம்)

சுயமுறைக்கு முன் சாத்தியம்; வரிசை → எஞ்சிய மீட்பு.

Pythonில் முயற்சி செய்வோம்

def valid_partition(nums: list[int], k: int, max_sum: int) -> bool:
    if k == 0:
        return True

    def dfs(i: int, cur: int, parts: int) -> bool:
        if parts == k:
            return i == len(nums)
        if cur == max_sum:
            return dfs(i, 0, parts + 1)
        if i == len(nums):
            return False
        if cur + nums[i] <= max_sum:
            if dfs(i + 1, cur + nums[i], parts):
                return True
        return False

    return dfs(0, 0, 0)


print(valid_partition([4, 3, 2, 3, 5, 2, 1], 4, 5))

பொதுவான தவறுகள்

• கடுமையான கத்தரிப்பு.
• முழு வெடிப்பு.

முக்கிய பாடங்கள்

• எதிர் உதாரணம் சோதனை.
• வரிசை dedupe.