C++에서 동일한 합계의 k-파티션으로 목록을 분할할 수 있는지 확인하는 프로그램

<시간/>

nums라는 숫자 목록과 다른 값 k가 있다고 가정하고 각 부분 집합의 합이 동일한 k개의 다른 부분 집합으로 num을 분할할 수 있는지 확인해야 합니다.

따라서 입력이 nums =[4, 2, 6, 5, 1, 6, 3] k =3과 같으면 출력은 다음과 같이 분할할 수 있으므로 True가 됩니다. [6, 3], [6 , 2, 1] 및 [4, 5].

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

check() 함수를 정의하면 배열 v가 필요합니다.
초기화 i의 경우:=1, i
v[i]가 v[0]과 같지 않으면 -
- 거짓 반환

참을 반환

dfs() 함수를 정의하면 idx, 배열 숫자, 배열 온도,

idx가 숫자의 크기와 같으면 -

반품 수표(임시)

ret :=거짓

초기화 i의 경우:=0, i <임시 크기일 때 업데이트(i를 1씩 증가), 수행 -

temp[i] :=temp[i] + 숫자[idx]
ret :=dfs(idx + 1, 숫자, 임시)
ret가 참이면 -
- 참을 반환
temp[i] :=temp[i] - 숫자[idx]

거짓 반환

메인 방법에서 다음을 수행하십시오 -

k 크기의 어레이 온도 정의

dfs(0, 숫자, 온도)를 반환

예시(C++)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool check(vector<int>& v) {
      for (int i = 1; i < v.size(); i++) {
         if (v[i] != v[0])
            return false;
      }
      return true;
   }
   bool dfs(int idx, vector<int>& nums, vector<int>& temp) {
      if (idx == nums.size()) {
         return check(temp);
      }
      bool ret = false;
      for (int i = 0; i < temp.size(); i++) {
         temp[i] += nums[idx];
         ret = dfs(idx + 1, nums, temp);
         if (ret)
            return true;
         temp[i] -= nums[idx];
      }
      return false;
   }
   bool solve(vector<int>& nums, int k) {
      vector<int> temp(k);
      return dfs(0, nums, temp);
   }
};
bool solve(vector<int>& nums, int k) {
   return (new Solution())->solve(nums, k);
}
int main(){
   vector<int> v = {4, 2, 6, 5, 1, 6, 3};
   int k = 3;
   cout << solve(v, 3);
}

입력

{4, 2, 6, 5, 1, 6, 3}, 3