สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums เราต้องตรวจสอบว่าเราสามารถแบ่งตัวเลขออกเป็นสองกลุ่มโดยที่ผลรวมขององค์ประกอบในทั้งสองกลุ่มเหมือนกันหรือไม่
ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[2, 3, 6, 5] ผลลัพธ์จะเป็น True เนื่องจากเราสร้างกลุ่มได้ดังนี้ [2, 6] และ [3, 5]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้
-
ทั้งหมด :=ผลรวมขององค์ประกอบทั้งหมดเป็น nums
-
ถ้าผลรวมเป็นเลขคี่
-
คืนค่าเท็จ
-
-
half :=ส่วนของจำนวนเต็ม / 2
-
dp :=รายการขนาด half + 1 และเติม false
-
dp[0] :=จริง
-
สำหรับแต่ละ num เป็น num ทำ
-
สำหรับฉันในช่วงครึ่งถึง 0 ลดลง 1 ทำ
-
ถ้า i>=num แล้ว
-
dp[i] :=dp[i] หรือ dp[i - num]
-
-
-
-
กลับ dp[ครึ่ง]
ตัวอย่าง
class Solution: def solve(self, nums): total = sum(nums) if total & 1: return False half = total // 2 dp = [True] + [False] * half for num in nums: for i in range(half, 0, -1): if i >= num: dp[i] |= dp[i - num] return dp[half] ob = Solution() nums = [2, 3, 6, 5] print(ob.solve(nums))
อินพุต
[2, 3, 6, 5]
ผลลัพธ์
True
