[LeetCode] 494. Target Sum

https://leetcode.com/problems/target-sum/

leetcode - Target Sum

문제 유형: 다이나믹 프로그래밍

문제 난이도: Medium

 

문제

You are given an integer array nums and an integer target.

You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.

• For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".

Return the number of different expressions that you can build, which evaluates to target.

 

정수 배열 nums와 정수 target이 주어진다.

nums의 각 수에 + 또는 - 부호를 줄 수 있다.

적절히 부호를 주어서 합이 target이 되는 모든 경우의 수를 구하시오.

 

풀이

탑다운 dp 또는 바텀업 dp 모두 가능하다.

여기서는 바텀업 dp로 한다.

전체를 합한 수 total을 기준으로 offset으로 정해서 dp테이블을 만든다.

dp[idx][prefix sum] = prefix sum을 만들기 위한 idx까지의 부분합 경우의수로 한다.

 

dp[n-1][target + total]의 값에 정답이 들어있다.

 

코드

C++

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int n = nums.size();
        int total = accumulate(nums.begin(), nums.end(), 0);

        vector<vector<int>> dp(n, vector<int>(2*total+1, 0));
        dp[0][nums[0] + total] = 1;
        dp[0][-nums[0] + total] += 1;

        for(int idx = 1; idx < n; ++idx) {
            for(int sum = -total; sum <= total; ++sum) {
                if(dp[idx-1][sum+total] > 0) {
                    dp[idx][sum + nums[idx] + total] += dp[idx-1][sum+total];
                    dp[idx][sum - nums[idx] + total] += dp[idx-1][sum+total];
                }
            }
        }

        return abs(target) > total? 0 : dp[n-1][target + total];
    }
};