nums라는 숫자 목록이 있다고 가정하고 두 그룹의 요소 합이 동일한 두 그룹으로num을 분할할 수 있는지 확인해야 합니다.
따라서 입력이 nums =[2, 3, 6, 5]와 같으면 출력은 [2, 6] 및 [3, 5]와 같은 그룹을 만들 수 있으므로 True가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다.
-
total :=num에 있는 모든 요소의 합
-
합계가 홀수이면
-
거짓을 반환
-
-
half :=전체의 정수 부분 / 2
-
dp :=절반 크기의 목록 + 1 및 false로 채우기
-
dp[0] :=참
-
숫자의 각 숫자에 대해 수행
-
0~0 범위의 i에 대해 1 감소, 수행
-
i>=num이면
-
dp[i] :=dp[i] 또는 dp[i - 숫자]
-
-
-
-
반환 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