C++의 조합 합 IV

모든 양수를 포함하는 정수 배열이 있고 모든 요소가 고유하다고 가정하고 가능한 조합의 수를 찾아 더하면 양의 정수 대상이 됩니다.

따라서 배열이 [1, 2, 3]이고 대상이 4이면 가능한 조합은 [[1,1,1,1], [1,1,2], [1,2,1]입니다. , [2,1,1], [1,3], [3,1], [2, 2]] 이므로 출력은 7이 됩니다.

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

• solve()라는 재귀 함수가 하나 있다고 가정하고 동적 프로그래밍 작업을 위해 배열, 대상 및 다른 배열을 사용합니다. 프로세스는 다음과 같습니다.
• 타겟 =0이면 1을 반환
• dp[target]이 -1이 아니면 dp[target]을 반환합니다.
• ans :=0
• 0에서 nums까지의 범위에 있는 i의 경우
  • 대상>=nums[i]
    인 경우
    • ans :=ans + solve(nums, target – nums[i], dp)
• dp[target] 설정 :=ans
• 반환

예(C++)

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int combinationSum4(vector<int>& nums, int target) {
      vector <int> dp(target + 1, -1);
      return helper(nums, target, dp);
   }
   int helper(vector <int>& nums, int target, vector <int>& dp){
      if(target == 0)return 1;
      if(dp[target] != -1)return dp[target];
      int ans = 0;
      for(int i = 0; i < nums.size(); i++){
         if(target >= nums[i]){
            ans += helper(nums, target - nums[i], dp);
         }
      }
      return dp[target] = ans;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,3};
   cout << ob.combinationSum4(v, 4);
}

입력

[1,2,3]
4

출력

7