C++에서 K 개의 동일한 합계 부분 집합으로 분할

nums라고 하는 정수 배열과 양의 정수 k가 있다고 가정하고 이 배열을 합이 모두 같은 k개의 비어 있지 않은 부분 집합으로 나눌 수 있는지 확인하십시오. 따라서 배열이 [4,3,2,3,5,2,1]이고 k =4인 경우 주어진 배열을 [[5], [ 1,4], [2,3], [2,3]] 합계가 동일합니다.

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

dp라는 두 개의 테이블을 정의하고 총 크기는 2^n,
주어진 배열 nums 정렬, set sum :=nums 배열에 있는 모든 요소의 합
sum mod k가 0이 아니거나 nums의 마지막 요소> sum / k이면 false를 반환합니다.
set dp[0] :=true 및 sum :=sum / k
0~2^n
- dp[i]가 0이 아니면
  - 0 ~ ,
    - temp :=i OR 2 ^ j
    - temp가 i와 같지 않으면
      - nums[j] <=sum – total[i] mod sum이면 dp[temp] :=true
      - total[temp] :=total[i] + nums[j]
    - 루프에서 나오지 않으면
반환 dp[(2^n) - 1]

예(C++)

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool canPartitionKSubsets(vector<int>& nums, int k) {
      int n = nums.size();
      vector <bool> dp(1 << n);
      vector <int> total(1 << n);
      sort(nums.begin(), nums.end());
      int sum = 0;
      for(int i = 0; i < nums.size(); i++)sum += nums[i];
      if(sum % k || nums[nums.size() - 1] > sum / k) return false;
      dp[0] = true;
      sum /= k;
      for(int i = 0; i < (1 << n); i++){
         if(dp[i]){
            for(int j = 0; j < n; j++){
               int temp = i | (1 << j);
               if(temp != i){
                  if(nums[j] <= sum - (total[i] % sum)){
                     dp[temp] = true;
                     total[temp] = total[i] + nums[j];
                  }
                  else{
                     break;
                  }
               }
            }
         }
      }
      return dp[(1 << n) - 1];
   }
};
main(){
   Solution ob;
   vector<int> v = {4,3,2,3,5,2,1};
   cout << (ob.canPartitionKSubsets(v, 4));
}

입력

[4,3,2,3,5,2,1]
4

C++에서 K 개의 동일한 합계 부분 집합으로 분할

예(C++)

입력

출력