Pruning (Early Stopping in Search Trees) — அடிப்படை

Pruning என்பது ஒரு சுயமுறை கிளை சரியான பதிலுக்கு வழிவகுக்காது என்று தெரிந்தவுடன் அதை நிறுத்துவது. குறைவான நோட்களை explore செய்து பெரிய தேடலில் TLE தவிர்க்கலாம்.

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

புதிர் தீர்ப்பி, அட்டவணை கருவிகள், நேர்காணல் backtracking — brute force மெதுவாக இருக்கும்; pruning DFS தேடலை நடைமுறைக்கு கொண்டு வரும்.

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

ஒவ்வொரு படியிலும்: இந்த பகுதி நிலை இன்னும் வெற்றி பெற முடியுமா? இல்லை என்றால் உடனே return.

பொதுவான சோதனைகள்:

• பகுதி கூட்டுத்தொகை target-ஐ மீறிவிட்டது.
• எஞ்சிய பட்ஜெட்டில் சிறிய மீதி பொருட்கள் பொருந்தாது.
• கட்டுப்பாடு ஏற்கனவே மீறப்பட்டது.

அடுத்த தேர்வுக்கு முன், சுயமுறையின் தொடக்கத்தில் சோதனை வையுங்கள்.

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

def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
    candidates.sort()
    res: list[list[int]] = []

    def dfs(start: int, remain: int, path: list[int]) -> None:
        if remain == 0:
            res.append(path.copy())
            return
        if remain < 0:
            return
        for i in range(start, len(candidates)):
            x = candidates[i]
            if x > remain:
                break
            path.append(x)
            dfs(i, remain - x, path)
            path.pop()

    dfs(0, target, [])
    return res


print(combination_sum([2, 3, 6, 7], 7))

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

• prune சோதனையை சுயமுறைக்குப் பிறகு வைப்பது — ஏற்கனவே வேலை செலவாகிவிடும்.
• கடுமையான pruning — சரியான பதில்களும் வெளியேறும்; சிறு counterexample உடன் சோதி.
• தோல்வி கிளைக்குப் பிறகு நிலை மீளமை மறப்பது.

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

• Pruning என்ன தேடுகிறோம் என்பதை மாற்றாது — உதவாத கிளைகளை வெட்டும்.
• x > remain இல் break பயன்படுத்தினால் உள்ளீட்டை வரிசைப்படுத்து.
• சிறு recursion மரம் வரை; pruning தவிர்க்கும் நோட்களை குறி.