Subset Sum with Backtracking — அடிப்படை

துணைக்கண மொத்தம் — சிறு n DFS; வரிசை கத்தரிப்பு.

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

ஒதுக்கீடு; பிரிவு; முட்டைச் சாவி.

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

இறங்கு வரிசை; எஞ்சிய மொத்தம் எல்லை.

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

def subset_sum(nums: list[int], t: int) -> bool:
    nums.sort(reverse=True)

    def dfs(i: int, cur: int) -> bool:
        if cur == t:
            return True
        if i == len(nums) or cur > t:
            return False
        return dfs(i + 1, cur + nums[i]) or dfs(i + 1, cur)

    return dfs(0, 0)


print(subset_sum([3, 34, 4, 12, 5, 2], 9))

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

• மிதவை T.
• இருப்பு எதிர் எண்ணி.

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

• meet-in-the-middle.
• சிறு மொத்தம்→DP.