مسئله مجموع زیرمجموعه‌ها (Subset Sum)
Subset Sum: پیدا کردن زیرمجموعه با جمع هدف — Backtracking با هرس، نسخه DP و مقایسه دو رویکرد
مسئله
آیا زیرمجموعه‌ای از اعداد با جمع دقیقاً هدف وجود دارد؟ [3, 34, 4, 12, 5, 2] و هدف ۹ ← بله: [4, 5]. مسئله کلاسیک NP-Complete!
رویکرد ۱: Backtracking با هرس
هر عنصر: بگیر/نگیر. دو هرس قدرتمند:
- هرس کسر: جمع فعلی + جمع همه باقی‌مانده < هدف ← بی‌فایده، قطع!
- هرس عبور: اعداد نامنفی: جمع فعلی > هدف ← قطع
رویکرد ۲: برنامه‌نویسی پویا
اگر هدف کوچک است (مثلاً ≤ ۱۰۰۰۰):
dp[j] = آیا جمع j قابل ساخت است؟
dp[0] = True (مجموعه خالی)
برای هر عدد x: dp[j] |= dp[j - x] (از j بزرگ به کوچک)O(n × target) — شبه‌چندجمله‌ای (هدف را «اندازه ورودی» فرض می‌کنیم).
مقایسه دو رویکرد
| ویژگی | Backtracking | DP |
|---|---|---|
| پیچیدگی | نمایی (با هرس کمتر) | O(n × target) |
| حافظه | O(n) پشته | O(target) |
| هدف بزرگ | بهتر ✓ | نامعملی! |
| اعداد منفی | ✓ کار می‌کند | سخت |
| خود زیرمجموعه | طبیعی ✓ | بازسازی لازم |
نسخه شمردن
«چند زیرمجموعه با جمع هدف؟» — همان DP اما شمارش: dp[j] += dp[j-x]. پایه مسائل شمارش ترکیبیاتی!
نکته: Subset Sum NP-Complete است یعنی احتمالاً راه‌حل چندجمله‌ای «همه‌حالته» ندارد — اما DP شبه‌چندجمله‌ای (وابسته به مقدار هدف) برای اهداف متوسط عالی جواب می‌دهد. انتخاب رویکرد = تحلیل اندازه ورودی!
جمع‌بندی
- بگیر/نگیر + هرس کسر و عبور = Backtracking
- DP: dp[j] قابل‌ساخت؟ — O(n × target)
- هدف بزرگ ← Backtracking؛ هدف کوچک ← DP
- نسخه شمارش: پایه مسائل ترکیبیاتی
این مبحث بخشی از دوره آموزش کامل الگوریتم‌ها است.