LeetCode #46 Permutations: สลับให้ครบทุกแถวโดยไม่ซ้ำตำแหน่ง

โจทย์ให้ลิสต์ตัวเลขไม่ซ้ำ แล้วคืนทุก permutation ครับ จำนวนคำตอบคือ n! — จุดพลาดคือใช้สมาชิกซ้ำหรือลืมคืนสถานะตอน backtrack

วิธีที่ 1: Backtracking + used[] — ค่าเริ่มต้นที่แนะนำ

เก็บ path ปัจจุบันและอาร์เรย์ used ลองใส่ตัวที่ยังไม่ใช้ แล้วถอยหลัง เวลา O(n·n!) หน่วยความจำสแต็ก O(n) ไม่นับ output

เหมาะ whiteboard และโค้ดโปรดักชันที่อ่านง่าย

วิธีที่ 2: สลับในที่ (swap in-place)

ที่ index i สลับกับ i..n-1 แล้ว recurse i+1 แล้วสลับกลับ ใช้หน่วยความจำเสริมน้อย ถ้าโจทย์อนุญาตแก้ลิสต์ต้นฉบับ

เหมาะเมื่ออยากโชว์ in-place และลดลิสต์ชั่วคราว

วิธีที่ 3: itertools.permutations (Python) / ไลบรารี

เร็วสำหรับงานสคริปต์ แต่ในสัมภาษณ์มักต้องเขียนเอง และต้องแปลงเป็นลิสต์ถ้าโจทย์ต้องการโครงสร้างเฉพาะ

เหมาะโปรโตไทป์/โปรดักชัน Python ที่ไม่ติดกรอบสัมภาษณ์

เลือกเมื่อไหร่: สัมภาษณ์ → วิธี 1 หรือ 2; สคริปต์จริงใน Python → วิธี 3; เน้น memory → วิธี 2

import unittest

def permute(nums):
    res = []
    used = [False] * len(nums)
    path = []
    def dfs():
        if len(path) == len(nums):
            res.append(path.copy())
            return
        for i, x in enumerate(nums):
            if used[i]:
                continue
            used[i] = True
            path.append(x)
            dfs()
            path.pop()
            used[i] = False
    dfs()
    return res

class TestPerm(unittest.TestCase):
    def test_three(self):
        got = sorted(permute([1, 2, 3]))
        self.assertEqual(len(got), 6)
        self.assertIn([1, 2, 3], got)
        self.assertIn([3, 2, 1], got)

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

Recap

• จำว่า output โตเป็น n! — บอกอินเตอร์วิวว์ก่อนลงโค้ด
• อย่าลืม undo (pop / สลับกลับ) ทุกครั้ง
• ถ้าตัวเลขซ้ำได้ ให้ใช้โจทย์ #47 แทน (ต้องข้าม duplicate)