ترکیب‌ها و جایگشت‌ها

سه مسئله خواهر

جایگشت‌ها — هر عنصر یک‌بار

در هر سطح، هر عنصر استفاده‌نشده را انتخاب کن:

def permute(nums):
    result = []
    def backtrack(path, remaining):
        if not remaining:
            result.append(path[:])
            return
        for i in range(len(remaining)):
            backtrack(path + [remaining[i]],
                      remaining[:i] + remaining[i+1:])
    backtrack([], nums)
    return result

ترکیب‌ها — ترتیب مهم نیست

ترفند طلایی: فقط به جلو! هر انتخاب از «بعد از آخرین انتخاب» شروع شود — تکرار [1,2] و [2,1] حذف می‌شود:

def combine(n, k):
    result = []
    def backtrack(start, path):
        if len(path) == k:
            result.append(path[:])
            return
        for i in range(start, n + 1):   # از start به بعد!
            path.append(i)
            backtrack(i + 1, path)       # بعدی: بعد از i
            path.pop()
    backtrack(1, [])
    return result

ترکیب با تکرار (عناصر تکراری)

سه تفاوت ظریف:

1. ورودی مرتب شود
2. در حلقه: i > start و nums[i] == nums[i-1] ← رد کن (تکرار در همین سطح)
3. backtrack با i (نه i+1) — عنصر قابل استفاده مجدد (اگر مجاز باشد)

پیچیدگی‌ها

• جایگشت: n! جواب × کار هر کدام O(n) ← O(n × n!)
• ترکیب: C(n,k) × O(k)
• زیرمجموعه: 2ⁿ × O(n)

همه نمایی‌اند — طبیعت «همه حالت‌ها»!

جمع‌بندی

• جایگشت: انتخاب از استفاده‌نشده‌ها
• ترکیب: «فقط به جلو» — حذف تکرار ترتیبی
• تکراری: مرتب + رد تکرار هم‌سطح
• همه نمایی — تعداد جواب‌ها همین‌قدرند