LeetCode #39 Combination Sum: เลือกซ้ำได้ แต่ห้ามสร้างคำตอบซ้ำ

โจทย์ให้จำนวนบวกไม่ซ้ำกันใน candidates และ target เราเลือกแต่ละจำนวนซ้ำได้ไม่จำกัด แล้วคืนทุก combination ที่ผลรวมเท่ากับเป้าหมายโดยห้ามคำตอบซ้ำครับ จุดที่พลาดบ่อยคือสร้างทั้ง [2, 3, 2] และ [3, 2, 2] ทั้งที่เป็นชุดเดียวกัน

ให้นึกถึงการตักวัตถุดิบจากชั้นวาง เราตักช่องเดิมซ้ำได้ แต่เมื่อเดินผ่านช่องหนึ่งไปแล้วจะไม่ย้อนกลับ วิธีนี้ทำให้ทุกชุดเกิดในลำดับเดียว จึงไม่ต้องสร้าง set ใหญ่มากรองผลลัพธ์ซ้ำทีหลัง

วิธีที่ 1: Include หรือ skip

ที่ index หนึ่ง เรามีสองทาง: หยิบค่านั้นแล้วอยู่ index เดิมเพราะเลือกซ้ำได้ หรือไม่หยิบแล้วไป index ถัดไป State คือ (index, remaining) โครงสร้างพิสูจน์ง่าย แต่ tree มี branch ที่เดินลึกมากเมื่อ candidate เล็ก เวลาแปรตามจำนวน state/คำตอบแบบ exponential ในกรณีทั่วไป และ stack ลึกได้ถึง target / min(candidates)

วิธีที่ 2: Sorted backtracking — ค่าเริ่มต้นที่แนะนำ

sort candidates แล้ว DFS จาก start ลองค่าตั้งแต่ตำแหน่งนั้น เมื่อค่ามากกว่า remaining ให้ break ได้ทันที การส่ง index เดิมเข้า recursion อนุญาตให้ใช้ค่าซ้ำ ส่วนการไม่ย้อน index กัน permutation ซ้ำ เวลาขึ้นกับจำนวนโหนดใน search tree และต้องใช้พื้นที่ stack/path O(target / minCandidate) ไม่นับ output

วิธีที่ 3: Bottom-up dynamic programming

ให้ dp[sum] เก็บ combinations ที่สร้างผลรวมนั้น วน candidate ด้านนอกและ sum จาก candidate ขึ้นไป เพื่อให้ลำดับ canonical และอนุญาตใช้ค่าเดิมซ้ำ เวลาและ memory ผูกกับจำนวน combinations ที่ materialize ในทุกผลรวมย่อย เหมาะเมื่อ target ไม่ใหญ่หรือต้องตอบหลาย target จาก candidate ชุดเดิม แต่กิน memory มากกว่าการค้นเฉพาะคำตอบปลายทาง

import unittest


def combination_include_skip(candidates, target):
    values = sorted(candidates)
    result = []

    def visit(index, remaining, path):
        if remaining == 0:
            result.append(path.copy())
            return
        if index == len(values) or values[index] > remaining:
            return
        path.append(values[index])
        visit(index, remaining - values[index], path)
        path.pop()
        visit(index + 1, remaining, path)

    visit(0, target, [])
    return result


def combination_backtracking(candidates, target):
    values = sorted(candidates)
    result = []

    def search(start, remaining, path):
        if remaining == 0:
            result.append(path.copy())
            return
        for index in range(start, len(values)):
            value = values[index]
            if value > remaining:
                break
            path.append(value)
            search(index, remaining - value, path)
            path.pop()

    search(0, target, [])
    return result


def combination_dp(candidates, target):
    dp = [[] for _ in range(target + 1)]
    dp[0] = [[]]
    for value in sorted(candidates):
        for total in range(value, target + 1):
            for previous in dp[total - value]:
                dp[total].append(previous + [value])
    return dp[target]


def normalized(groups):
    return sorted(tuple(group) for group in groups)


class CombinationSumTests(unittest.TestCase):
    def test_methods_and_edges(self):
        cases = [
            ([2], 1, []),
            ([2, 3, 6, 7], 7, [(2, 2, 3), (7,)]),
            ([2, 3, 5], 8, [(2, 2, 2, 2), (2, 3, 3), (3, 5)]),
        ]
        for candidates, target, expected in cases:
            for method in (combination_include_skip, combination_backtracking, combination_dp):
                with self.subTest(method=method.__name__, target=target):
                    self.assertEqual(normalized(method(candidates, target)), sorted(expected))


if __name__ == "__main__":
    unittest.main()

เลือกตามสถานการณ์

เงื่อนไข	Include-skip	Sorted backtracking	Bottom-up DP
input/target ใหญ่	branch เยอะ	pruning ดีเมื่อ sort	ตารางและ output ย่อยโต
memory จำกัด	path + stack	path + stack	เก็บชุดของทุก sum
readability	recurrence ชัด	กระชับและตรงโจทย์	state ชัดแต่ allocation มาก
sorted/streaming input	sort ก่อนเพื่อ prune	sort ก่อน; ไม่ใช่ streaming	ต้องมี candidates ครบ
การแก้ input	ใช้สำเนาที่ sort	ใช้สำเนาที่ sort	ใช้สำเนาที่ sort

best default ภายใต้ constraints ของโจทย์คือ sorted backtracking เพราะกัน permutation ซ้ำตั้งแต่กำเนิด ตัด branch ได้เร็ว และเก็บเฉพาะ path ปัจจุบันนอก output

Edge cases

โจทย์รับประกัน candidate เป็นจำนวนบวกและไม่ซ้ำ เงื่อนไขนี้ทำให้ recursion จบ หากรับศูนย์หรือติดลบจากระบบจริง ต้อง reject ก่อนเพราะ remaining อาจไม่ลด ทดสอบกรณีไม่มีคำตอบ, candidate เท่ากับ target และคำตอบที่ใช้ค่าเดิมหลายครั้ง

Recap

• จำกัดการเลือกไว้ตั้งแต่ start เพื่อไม่สร้าง permutation ซ้ำ
• เรียงข้อมูลแล้ว break เมื่อค่าปัจจุบันเกิน remaining
• backtracking เป็น default ที่สมดุลเวลาและ memory
• DP เหมาะเมื่อ target เล็กหรือ reuse ตารางกับหลาย query