Giả sử chúng ta có một danh sách các số được gọi là num, chúng ta phải kiểm tra xem chúng ta có thể phân vùng thành hai nhóm mà tổng các phần tử trong cả hai nhóm đều bằng nhau hay không.
Vì vậy, nếu đầu vào giống như nums =[2, 3, 6, 5], thì đầu ra sẽ là True, vì chúng ta có thể tạo các nhóm giống như:[2, 6] và [3, 5].
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau
-
Total:=tổng của tất cả các phần tử trong nums
-
nếu tổng là số lẻ thì
-
trả về Sai
-
-
một nửa:=phần nguyên của tổng số / 2
-
dp:=danh sách kích thước nửa + 1 và điền sai
-
dp [0]:=true
-
đối với mỗi số trong số, thực hiện
-
đối với tôi trong phạm vi một nửa đến 0, giảm đi 1, thực hiện
-
nếu tôi> =num, thì
-
dp [i]:=dp [i] HOẶC dp [i - num]
-
-
-
-
trả về dp [một nửa]
Ví dụ
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))
Đầu vào
[2, 3, 6, 5]
Đầu ra
True