Subset Sum with Backtracking

Subset sum asks if any subset hits T—NP-complete in general but small n allows DFS with pruning on sorted descending values to fail fast.

Why this shows up in the real world

Resource allocation, partition problems, and cryptography knapsack variants (conceptually).

Core idea (explained for students)

Sort descending, branch on include first large numbers, prune when partial + sum(remaining) < T impossible check with sorted prefix sums.

Try this in 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))

Common mistakes

• Floating T with precision—use integers scaled.
• Counting vs existence—different return types.

Key takeaways

• Meet-in-the-middle for n≈40 split halves.
• DP bitmask when sum range small (subset sum DP).