음이 아닌 정수 a1, a2, ..., an 및 또 다른 값, 즉 대상 S의 목록이 있다고 가정합니다. 이제 2개의 기호 + 및 -가 있습니다. . 각 정수에 대해 새 기호로 +와 - 중에서 하나를 선택해야 합니다. 정수의 합을 목표 값 S와 같게 하기 위해 기호를 할당하는 방법의 수를 찾아야 합니다. 따라서 숫자가 [1,1,1,1,1]이고 S =3이면 출력은 다음과 같습니다. 5, 조합은 – 1 + 1 + 1 + 1 + 1 =3, + 1 – 1 + 1 + 1 + 1 =3, + 1 + 1 – 1 + 1 + 1 =3, + 1 + 1 +이므로 1 – 1 + 1 =3, + 1 + 1 + 1 + 1 – 1 =3. 따라서 할당하는 방법은 5가지가 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 크기가 21 x 2001인 하나의 테이블 dp를 만들고 여기에 - 1을 채웁니다. 이것은 동적 프로그래밍 접근 방식에 사용됩니다.
- 재귀적 메서드는 solve()라는 이름으로 사용됩니다. 이것은 pos, 배열 v, tempSum 및 실제 합계 S를 취합니다. 이것은 아래와 같이 작동합니다 -
- pos가 배열 v의 크기와 같으면 s =tempSum이면 true를 반환하고 그렇지 않으면 false를 반환합니다.
- dp[pos, tempSum + 1000]이 -1이 아니면 dp[pos, tempSum + 1000]을 반환합니다.
- ans :=solve(pos + 1, v, tempSum – v[pos], s) + solve(pos + 1, v, tempSum + v[pos], s)
- dp[pos, tempSum + 1000] =ans
- 반환
- 매개변수 solve(0, nums, 0, s)를 사용하여 메인 섹션에서 solve() 호출
예(C++)
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int dp[21][2001];
int solve(int pos, vector <int> v, int tempSum, int s){
if(pos == v.size()){
return s == tempSum;
}
if(dp[pos][tempSum+1000]!=-1)return dp[pos][tempSum+1000];
int ans = solve(pos+1,v,tempSum-v[pos],s) +solve(pos+1,v,tempSum+v[pos],s);
dp[pos][tempSum+1000] = ans;
return ans;
}
int findTargetSumWays(vector<int>& nums, int s) {
int n = nums.size();
if(s>1000)return 0;
for(int i =0;i<21;i++){
for(int j =0;j<2001;j++){
dp[i][j] = -1;
}
}
return solve(0,nums,0,s);
}
};
main(){
Solution ob;
vector<int> v = {1,1,1,1,1};
cout << ob.findTargetSumWays(v, 3);
} 입력
[1,1,1,1,1] 3
출력
5