[leetcode 494] Target Sum

문제: 주어진 모든 수 앞에 +나 -를 붙여서 계산한다. 계산값이 S와 동일한 경우를 카운트

Example 1:

Input: nums is [1, 1, 1, 1, 1], S is 3.

Output: 5

Explanation: -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 There are 5 ways to assign symbols to make the sum of nums be target 3.

 

Constraints:

• The length of the given array is positive and will not exceed 20.
• The sum of elements in the given array will not exceed 1000.
• Your output answer is guaranteed to be fitted in a 32-bit integer.

 

모든 수는 양수로 주어진다.

 

--처음 풀이: 재귀를 이용한 Brute Force

-> 시간 초과 났다. 

->> 수정: nums를 인자로 받기 위해선 참조자&를 사용해야 한다. 아니면 계속 벡터를 복사하기 때문에 불필요한 시간이 소요됨

아래는 TLE 안남

class Solution {
public:
    int answer;
    vector<int> num;
    void Recursive(int res, int cnt, int goal){
        if(cnt == num.size()){
            if(res == goal){
                answer++;
            }   
            return;
        }
        
     
        Recursive(res+num[cnt], cnt+1, goal);
        Recursive(res-num[cnt], cnt+1, goal);
        
    }
    
    int findTargetSumWays(vector<int>& nums, int S) {
        
      
        answer = 0;
        //back tracking
        num = nums;
        
        Recursive(0, 0, S);
        return answer;
    }
};

 

-- 역시 DP로 풀어야 한다.

- 그럼 무엇을 dp로 두는가가 초점이 된다. 여기서 dp 값은 경우의 수로 잡는다. 

dp[j]는 합이 j가 되는 경우의 수가 될 것이다.

 

 

 

dp[i][target] = 숫자가 [0 ,,, i]까지 있는 배열 내에서 그 합이 target인 subset의 수 라 정의하자. 그렇다면

dp[i+1][target] = dp[i][target] + dp[i][target - nums[i+1]]

-> [0,,,i+1]까지의 숫자로 target을 만들기 위해선 = i까지 숫자로  target만들기 + i까지 숫자론 target-(i+1번째 숫자)만큼만 만들기가 되어야 한다.

 

그러면 우리가 구하고자 하는 값은 주어진 배열의 사이즈만큼의 숫자를 사용해서 s를 만드는 것이다. 

즉 dp[v.size()-1][s]를 return한다.

 

초기화:

dp[0][nums[0]] = 1

dp[0][-nums[0]] = 1

 

dp[i][j]일 때, i는 j를 만들기 위해 사용되는 숫자의 수, j는 목적 값이다.

아래는 문제 조건에서 배열 합이 1000을 넘지 않는다고 했기 때문에 배열에 담기 위해 idx를 양수로 만들기 위해 1000을 더해준것이다.

 

j만 설명하자면 이런 모양새가 나온다

갤텝 사고 싶다

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

class Solution{
public:
    int findTargetSumWays(vector<int> &nums, int S) {
    
        int dp[nums.size()][2001] ={0,};
        dp[0][nums[0] + 1000] = 1; 
        dp[0][-nums[0] + 1000] += 1; //+=1 인 이유는 nums[0]=0인 경우도 존재하기 때문이다.
        for (int i = 1; i < nums.length; i++) {
            for (int sum = -1000; sum <= 1000; sum++) {
                if (dp[i - 1][sum + 1000] > 0) { //이전 경우의 수가 존재한다면
                //1000을 더하는 이유는 배열 인덱스를 0이상으로 만들기 위해서..
                
                    dp[i][sum + nums[i] + 1000] += dp[i - 1][sum + 1000]; 
                    dp[i][sum - nums[i] + 1000] += dp[i - 1][sum + 1000];
                }
            }
        }
        return S > 1000 ? 0 : dp[nums.length - 1][S + 1000];
    }
}

 

하지만 문제의 조건을 보면 dp가 굳이 이차원배열이 아녀도 된다는 사실을 알 수 있다

왜냐하면 우리는 배열 원소 전부를 사용해야 하기 때문 즉, dp[i][j]에서 i는 n-1로 고정이기 때문에 따지지 않는다.

 

public class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int[] dp = new int[2001];
        dp[nums[0] + 1000] = 1;
        dp[-nums[0] + 1000] += 1;
        for (int i = 1; i < nums.length; i++) {
            int[] next = new int[2001];
            for (int sum = -1000; sum <= 1000; sum++) {
                if (dp[sum + 1000] > 0) {
                    next[sum + nums[i] + 1000] += dp[sum + 1000];
                    next[sum - nums[i] + 1000] += dp[sum + 1000];
                }
            }
            dp = next;
        }
        return S > 1000 ? 0 : dp[S + 1000];
    }
}