0Pricing
DSA Interview Prep · บทเรียน

ผลรวมเป้าหมายพร้อมเครื่องหมายบวกและลบ

แปลงปัญหาการกำหนดเครื่องหมายของผลรวมเป้าหมายให้เป็นปัญหากระเป๋าเป้บนผลต่างของผลรวมเซตย่อย และแก้ในเวลา O(n × sum)

ผลรวมเป้าหมายพร้อมเครื่องหมายบวกและลบ เป็นบทเรียน DSA Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน DSA Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส DSA Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน

ปัญหาผลรวมเป้าหมาย

กำหนดอาร์เรย์จำนวนเต็ม nums และจำนวนเต็ม target ให้กำหนดเครื่องหมาย + หรือ - ให้กับตัวเลขแต่ละตัว เพื่อให้นิพจน์ที่ได้มีค่าเป็น target ให้คืนค่าจำนวนวิธีที่แตกต่างกันในการทำเช่นนี้ ตัวอย่างเช่น เมื่อ nums=[1,1,1,1,1] และ target=3 จะมีทั้งหมด 5 วิธี (เลือกสมาชิก 4 ตัวให้เป็นบวก และอีก 1 ตัวให้เป็นลบ โดยตำแหน่งที่เลือกแตกต่างกัน)

การไล่ครบทุกกรณี: การแจกแจงด้วย DFS

วิธี DFS กำหนดเครื่องหมาย + หรือ - ให้กับตัวเลขแต่ละตัวและเรียกตัวเองแบบเวียนเกิด โดยคืนค่าจำนวนโหนดปลายที่มีค่าเป็น target วิธีนี้ถูกต้อง แต่มี ความซับซ้อนด้านเวลา O(2^n) ซึ่งเป็นแบบเอ็กซ์โพเนนเชียล สำหรับ n=20 จะมีการเรียกฟังก์ชันเวียนเกิดมากกว่าหนึ่งล้านครั้ง ควรกล่าวถึงวิธี DFS ก่อน แล้วจึงเปลี่ยนไปสู่วิธีปรับปรุงด้วย DP อย่างรวดเร็ว

def findTargetSumWays_dfs(nums, target):
    count = [0]
    
    def dfs(i, current_sum):
        if i == len(nums):
            if current_sum == target:
                count[0] += 1
            return
        dfs(i+1, current_sum + nums[i])
        dfs(i+1, current_sum - nums[i])
    
    dfs(0, 0)
    return count[0]

print(findTargetSumWays_dfs([1,1,1,1,1], 3))  # 5

DFS พร้อมการจดจำผลลัพธ์

เพิ่มการจดจำผลลัพธ์ให้กับ DFS: สถานะคือ (index, current_sum) เนื่องจากผลรวมปัจจุบันอาจอยู่ในช่วงตั้งแต่ -total ถึง +total จึงมีสถานะที่ไม่ซ้ำกันจำนวน O(n × ผลรวมทั้งหมด) เมื่อใช้การจดจำผลลัพธ์ DFS จะทำงานด้วย เวลาและพื้นที่ O(n × ผลรวมทั้งหมด) วิธีนี้ใช้งานได้และเป็นคำตอบที่ยอมรับได้ในการสัมภาษณ์ แต่ DP ที่อาศัยการแปลงมีความสง่างามและประหยัดพื้นที่มากกว่า

from functools import lru_cache

def findTargetSumWays_memo(nums, target):
    total = sum(nums)
    
    @lru_cache(maxsize=None)
    def dp(i, remaining):
        if i == len(nums):
            return 1 if remaining == 0 else 0
        return dp(i+1, remaining - nums[i]) + dp(i+1, remaining + nums[i])
    
    return dp(0, target)

print(findTargetSumWays_memo([1,1,1,1,1], 3))  # 5

การแปลงทางคณิตศาสตร์

ให้ P เป็นเซตของตัวเลขที่กำหนดเครื่องหมาย + และ N เป็นเซตของตัวเลขที่กำหนดเครื่องหมาย - ดังนั้น: sum(P) - sum(N) = target และ sum(P) + sum(N) = total เมื่อนำมาบวกกัน: 2 × sum(P) = target + total ดังนั้น sum(P) = (target + total) / 2 ปัญหาจึงลดรูปเป็น: นับเซตย่อยของ nums ที่มีผลรวมเป็น (target + total) / 2 ซึ่งตรงกับปัญหากระเป๋าเป้ 0/1 รูปแบบการนับเซตย่อยพอดี

# sum(P) - sum(N) = target
# sum(P) + sum(N) = total
# => 2*sum(P) = target + total
# => sum(P) = (target + total) / 2
# Count subsets with sum = new_target = (target + total) // 2
print('Reduction: count subsets summing to (target + total) // 2')

การตรวจสอบความถูกต้องก่อนใช้ DP

ก่อนเรียกใช้ DP ให้ตรวจสอบว่า: (1) target + total ต้องเป็น จำนวนคู่ (มิฉะนั้น sum(P) จะไม่เป็นจำนวนเต็ม จึงเป็นไปไม่ได้) (2) abs(target) > total หมายความว่าไม่สามารถทำให้ถึงเป้าหมายได้ แม้กำหนดเครื่องหมายทั้งหมดไปในทิศทางเดียวกัน หากการตรวจสอบข้อใดข้อหนึ่งไม่ผ่าน ให้คืนค่า 0 ทันที การตรวจสอบเหล่านี้จัดการกรณีขอบได้อย่างเป็นระเบียบ โดยไม่ต้องเขียนเงื่อนไขเฉพาะกรณีไว้ภายในลูป DP

def findTargetSumWays(nums, target):
    total = sum(nums)
    if (target + total) % 2 != 0:
        return 0  # sum(P) would be non-integer
    if abs(target) > total:
        return 0  # impossible to reach
    new_target = (target + total) // 2
    # Count subsets summing to new_target
    dp = [0] * (new_target + 1)
    dp[0] = 1
    for num in nums:
        for c in range(new_target, num - 1, -1):
            dp[c] += dp[c - num]
    return dp[new_target]

print(findTargetSumWays([1,1,1,1,1], 3))  # 5

ไล่ตามตัวอย่างขนาดเล็ก

สำหรับ nums=[1,1,1,1,1] และ target=3: ผลรวมทั้งหมด=5, เป้าหมายใหม่=(3+5)//2=4 เรานับเซตย่อยที่มีผลรวมเป็น 4 จาก [1,1,1,1,1] ซึ่งเท่ากับ C(5,4)=5 (เลือกเลข 1 จำนวน 4 ตัวให้เป็นบวก และตัวที่ 5 เป็นลบ: 1+1+1+1-1=3) DP จะคืนค่า 5 ได้อย่างถูกต้อง การแปลงนี้เชื่อมโยงปัญหาการกำหนดเครื่องหมายเข้ากับปัญหาการนับเซตย่อยมาตรฐานได้อย่างงดงาม

การจัดการเลขศูนย์ในอาร์เรย์ตัวเลข

หาก nums มีเลขศูนย์ การกำหนดเครื่องหมาย + หรือ - ให้เลขศูนย์จะไม่เปลี่ยนผลรวม เลขศูนย์แต่ละตัวจึงเพิ่มจำนวนการกำหนดเครื่องหมายที่ถูกต้องเป็นสองเท่า DP จัดการกรณีนี้ได้โดยธรรมชาติ: เมื่อประมวลผล num=0 ลูปด้านใน range(new_target, -1, -1) จะวนจาก new_target ลงมาถึง 0 และ dp[c] += dp[c - 0] = dp[c] จะเพิ่มค่าของผลรวมที่ไปถึงได้ทั้งหมดเป็นสองเท่า ไม่จำเป็นต้องจัดการเป็นกรณีพิเศษ หากใช้ range(new_target, num-1, -1) ซึ่งเมื่อ num=0 จะเริ่มจาก new_target และวนลงมาถึง 0

# With zeros: each zero doubles the count
print(findTargetSumWays([0, 0, 1], 1))  # 4
# Assignments: +0+0+1, +0-0+1, -0+0+1, -0-0+1 = all give sum 1

การเปรียบเทียบความซับซ้อน

DFS แบบไล่ครบทุกกรณีมีความซับซ้อน O(2^n) DFS ที่จดจำผลลัพธ์มี เวลา O(n × ผลรวมทั้งหมด) และ พื้นที่ O(n × ผลรวมทั้งหมด) ส่วน DP 1 มิติที่อาศัยการแปลงมี เวลา O(n × new_target) และ พื้นที่ O(new_target) โดยที่ new_target ≤ total DP 1 มิติใช้พื้นที่น้อยกว่าการจดจำผลลัพธ์อย่างมาก เพราะตัดมิติของดัชนีออกไปผ่านการแปลง

การเชื่อมโยงกับปัญหากระเป๋าเป้ประเภทอื่น

ปัญหาผลรวมเป้าหมายเชื่อมโยงแนวคิดเกี่ยวกับกระเป๋าเป้หลายอย่างเข้าด้วยกัน: เริ่มต้นจากปัญหาการกำหนดค่า แปลงเป็นปัญหาผลรวมของเซตย่อย (เช่นเดียวกับการแบ่งอาร์เรย์เป็นเซตย่อยที่มีผลรวมเท่ากัน) และใช้แม่แบบการวนซ้ำย้อนกลับของกระเป๋าเป้ 0/1 เดิม แต่เปลี่ยนเป็นการนับ (เช่นเดียวกับการทอนเหรียญ II) การเข้าใจความเชื่อมโยงเหล่านี้ช่วยให้คุณจัดประเภทปัญหาใหม่ในการสัมภาษณ์ได้อย่างรวดเร็ว โดยพิจารณาจากความคล้ายคลึงเชิงโครงสร้างกับรูปแบบที่รู้จัก

กรณีขอบและข้อสังเกตสำหรับการสัมภาษณ์

กรณีสำคัญ ได้แก่ (1) target = total: มีเพียงหนึ่งวิธี (เป็นบวกทั้งหมด) (2) target = -total: มีเพียงหนึ่งวิธี (เป็นลบทั้งหมด) (3) target = 0 เมื่อเป็นเลขศูนย์ทั้งหมด: คำตอบคือ 2^n (4) ผลรวมทั้งหมดมีขนาดใหญ่มากแต่ n มีขนาดเล็ก — ขนาดอาร์เรย์ DP 1 มิติถูกจำกัดไว้ที่ total/2 ในการสัมภาษณ์ ควรอธิบายขั้นตอนการแปลงด้วยวาจาก่อนเขียนโค้ด เพราะนี่คือแนวคิดสำคัญที่ไม่เห็นได้โดยตรงและช่วยแยกผู้สมัครที่มีความเข้าใจดีออกจากผู้สมัครทั่วไป

ทางเลือก DP 2 มิติโดยไม่ใช้การแปลง

หากไม่ใช้การแปลง ให้กำหนด dp[i][s] = จำนวนวิธีในการกำหนดเครื่องหมายให้ตัวเลข i ตัวแรกแล้วได้ผลรวมเป็น s ผลรวมอาจเป็นลบได้ จึงเลื่อนค่าด้วยผลรวมทั้งหมด โดยใช้ dp[i][s + total] วิธีนี้ต้องใช้ตาราง 2 มิติขนาด (n+1) × (2*total+1) แม้จะถูกต้อง แต่ใช้พื้นที่มากกว่าและเขียนได้ยากกว่าภายใต้แรงกดดันจากการสัมภาษณ์ เมื่อเทียบกับกระเป๋าเป้ 1 มิติหลังการแปลง

ตรวจสอบความเข้าใจอย่างรวดเร็ว

ทดสอบความเข้าใจแนวคิดเรื่องโครงสร้างข้อมูลและอัลกอริทึม — การเตรียมตัวสัมภาษณ์การเขียนโปรแกรมจากบทเรียนนี้

สรุปบทเรียน

ในบทเรียนนี้ คุณได้เรียนรู้ว่า ปัญหาผลรวมเป้าหมายแปลงปัญหาการกำหนดเครื่องหมายให้กลายเป็นการนับเซตย่อยที่มีผลรวมเป็น (target + total) / 2 กระเป๋าเป้ 0/1 แบบ 1 มิติที่ใช้การวนซ้ำย้อนกลับจะนับเซตย่อยได้ในเวลา O(n × new_target) และพื้นที่ O(new_target) และ การตรวจสอบความถูกต้องล่วงหน้า (ผลรวมเป็นจำนวนคี่, |target| > total) ช่วยป้องกันการเรียกใช้ DP โดยไม่จำเป็น ต่อไปเราจะเข้าสู่เรื่องเส้นทางสั้นที่สุดด้วยอัลกอริทึม Dijkstra และคิวลำดับความสำคัญ

คำถามที่พบบ่อย

บทเรียน “ผลรวมเป้าหมายพร้อมเครื่องหมายบวกและลบ” ฟรีหรือไม่

ใช่ — ข้อความเต็มของ “ผลรวมเป้าหมายพร้อมเครื่องหมายบวกและลบ” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส DSA Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส DSA Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน

คุณจะเรียนรู้อะไรในบทเรียน “ผลรวมเป้าหมายพร้อมเครื่องหมายบวกและลบ”

แปลงปัญหาการกำหนดเครื่องหมายของผลรวมเป้าหมายให้เป็นปัญหากระเป๋าเป้บนผลต่างของผลรวมเซตย่อย และแก้ในเวลา O(n × sum) คุณปฏิบัติ DSA Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน

คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน DSA Interview Prep หรือไม่

ไม่จำเป็นต้องมีประสบการณ์มาก่อน DSA Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน

บทเรียน “ผลรวมเป้าหมายพร้อมเครื่องหมายบวกและลบ” ใช้เวลานานแค่ไหน

บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย

ฉันเขียนและรันโค้ดในบทเรียน DSA Interview Prep นี้ได้ไหม

ได้ บทเรียน DSA Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ

บทเรียนทั้งหมดในหลักสูตรนี้

  1. กระเป๋าเป้ 0/1 และการลดการใช้หน่วยความจำ
  2. กระเป๋าเป้ไม่จำกัดจำนวนและการทอนเหรียญ II
  3. ผลรวมเซตย่อยเท่ากันของการแบ่งพาร์ทิชัน
  4. ผลรวมเป้าหมายพร้อมเครื่องหมายบวกและลบ
← กลับไปที่ DSA Interview Prep