C++의 파티션 같음 부분집합 합계

양수만 포함하는 비어 있지 않은 배열이 있다고 가정하면 배열이 두 하위 집합의 요소 합계가 같도록 두 하위 집합으로 분할될 수 있는지 찾아야 합니다. 따라서 입력이 [1,5,11,5]와 같으면 출력이 true가 됩니다. 이 배열은 [1, 5, 5] 및 [11]

로 분할될 수 있으므로

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=배열의 크기
합계 :=0
i:=0 ~ n – 1
- 합계 :=합 + 숫자[i]
합계가 홀수이면 false를 반환
합계 :=합 / 2
Sum + 1 크기의 dp라는 배열 하나 만들기
dp[0] :=사실
0 ~ n – 1 범위의 i에 대해
- x :=숫자[i]
- for j :=j로 요약 – x
  - dp[j] :=dp[j] 또는 dp[j - x](0이 아님)
dp[합계]를 반환

예(C++)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool canPartition(vector<int>& nums) {
      int n = nums.size();
      int sum = 0;
      for(int i =0;i<n;i++)sum+=nums[i];
      if(sum&1)return false;
      sum/=2;
      vector <bool> dp(sum+1);
      dp[0] = true;
      for(int i =0;i<n;i++){
         int x = nums[i];
         for(int j =sum;j-x>=0;j--){
            dp[j]=dp[j] || dp[j-x];
         }
      }
      return dp[sum];
   }
};
main(){
   Solution ob;
   vector<int> v = {1,5,11,5};
   cout << ob.canPartition(v);
}

입력

[1,5,11,5]