공부 기록

nums 배열에 있는 값을 적절히 더하고 빼서 target과 같은 값을 만들 수 있는 방법의 수를 구하는 문제이다.

일단 문제를 풀 수 있는 방법으로 가장 먼저 떠오른 것은 브루트 포스,,, 시간복잡도는 O(2^N)이다.

class Solution {
	public int answer = 0;

	public int findTargetSumWays(int[] nums, int S) {
		findAll(nums, 0, 0, S);
		return answer;
	}

	public void findAll(int[] nums, int index, int sum, int target) {
		if (index >= nums.length) {
			if (sum == target) {
				answer++;
			}
			return;
		}

		findAll(nums, index + 1, sum - nums[index], target);
		findAll(nums, index + 1, sum + nums[index], target);
	}
}

이 방법 외에 다른 방법이 있지 않을까 생각해 봤다.

• 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.

문제 조건을 다시 보면 num의 합은 1000을 넘지 않는다고 했다.

합이 있으면 차도 가능하니 num을 적절히 더하고 빼면 그 범위는 -1000~1000일것이다.

이를 dp를 이용해서 구하도록 하는데, 음수 인덱스는 불가능 하니

dp[i][sum+1000]: num의 i번째 요소까지 더하고 뺐을 때, sum을 만들 수 있는 가짓수로 정의하도록 한다. 이 경우 시간복잡도는 O(N)이다.

import java.util.*;
class Solution {
	public int findTargetSumWays(int[] nums, int S) {
		int[][] memo = new int[nums.length][2001];
		for (int[] row : memo) {
			Arrays.fill(row, Integer.MIN_VALUE);
		}
		return calculate(nums, 0, 0, S, memo);
	}

	public int calculate(int[] nums, int i, int sum, int S, int[][] memo) {
		if (i == nums.length) {
			if (sum == S) {
				return 1;
			}
			return 0;
		}

		if (memo[i][sum + 1000] != Integer.MIN_VALUE) {
			return memo[i][sum + 1000];
		}

		int add = calculate(nums, i + 1, sum + nums[i], S, memo);
		int subtract = calculate(nums, i + 1, sum - nums[i], S, memo);
		memo[i][sum + 1000] = add + subtract;
		return memo[i][sum + 1000];
	}
}