target sum 부분집합 갯수 세기

 

nums=[1,2,1], target=3일 때, nums에서 원소의 합이 target인 부분집합은 몇 개일까?

답은 (1,2), (2,1)로 2개이다.

그렇다면 이를 구하기 위한 알고리즘은 무엇일까?

이러한 문제를 counting subsets with given sum이라 한다. 다른 문제에도 자주 이용되니 알아두자!

 

가능한 모든 경우를 파악해보면 된다. 그런데 이 때, 각 숫자는 합에 포함되거나 안되거나 둘 중 하나의 선택지를 갖는다. 그림으로 나타내면 아래와 같다.

 

이를 풀기 위해선 dp를 사용하면 된다.

 

위와 같이 dp를 모두 채운 뒤 dp[-1][-1]이 답이 된다.

 

관련 문제

---

leetcode.com/problems/target-sum/

Target Sum - LeetCode