leetcode416. Partition Equal Subset Sum
Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Note:
1.Each of the array element will not exceed 100.
2.The array size will not exceed 200.
Example 1:
Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
Input: [1, 2, 3, 5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.전체 정수 가 아 닌 빈 배열 이 있다 고 가정 하고 그 중의 숫자 를 두 부분 으로 나 누 어 두 부분의 숫자 와 똑 같은 것 을 확보한다.
아이디어 와 코드
이것 은 0 - 1 가방 문제 와 똑 같 습 니 다. 01 가방 문 제 는 n 개의 물품 이 있다 고 가정 하고 모든 물품 중 weight [i] 를 말 합 니 다. 가방 의 하중 이 k 라 고 가정 하고 물품 을 어떻게 선택 하여 가방 의 하중 을 가장 크게 하 는 지 물 어 봅 니 다.여기 서 문 제 는 n 개의 물품 이 있 고 모든 물품 의 무 게 는 inpuut [i] 입 니 다. 물품 을 어떻게 고 르 느 냐 고 물 어보 면 가방 의 무 게 를 모든 물품 의 무게 와 일반 으로 만 들 수 있 습 니 다.
만약 에 우리 가 앞의 i 개 물품 이 중량 k 를 구성 할 수 있 는 지 를 알 고 있다 면 우 리 는 이 값 을 dpi 로 한다. 그러면 i + 1 개 물품 이 무 게 를 구성 할 수 있 는 지 여 부 는 dpi 와 dpi 에 달 려 있다. 즉, i + 1 개 물품 이 중량 k 를 구성 할 수 있 는 지 두 가지 상황 이 있다. 첫 번 째 는 i + 1 개 물품 을 선택 하면 앞의 i 개 물품 이 k - input [i + 1] 의 무 게 를 구성 하 는 지, 두 번 째 는 i + 1 개 물품 을 선택 하지 않 은 것 이다.앞의 i 개 아 이 템 이 k 의 무 게 를 구 성 했 는 지 직접 판단 합 니 다.
코드 는 다음 과 같 습 니 다:
public boolean canParition(int[] nums) {
int sum = 0;
for(int n : nums) {
sum += n;
}
if(sum % 2 != 0) return false;
int half = sum / 2;
boolean[][] sums = new boolean[nums.length+1][half+1];
for(int i = 0 ; i<=nums.length ; i++) {
for(int j = 0 ; j<=half ; j++) {
if(i==0 && j==0){
sums[i][j] = true;
}else if(i==0) {
sums[i][j] = false;
}else if(j==0){
sums[i][j] = true;
}else {
sums[i][j] = sums[i-1][j] || (nums[i-1] <= j ? sums[i-1][j-nums[i-1]] : false);
}
}
}
return sums[nums.length][half];
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
0부터 시작하는 LeetCode Day8 「1302. Deepest Leaves Sum」해외에서는 엔지니어의 면접에 있어서 코딩 테스트라고 하는 것이 행해지는 것 같고, 많은 경우, 특정의 함수나 클래스를 주제에 따라 실장한다고 하는 것이 메인이다. 빠른 이야기가 본고장에서도 행해지고 있는 것 같은 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
