부분집합의 합

문제

이한은 정수 $N$개를 받았다. 이 가운데 몇 개를 골라 합이 $S$가 되게 하는 방법의 수를 구한다. 하나도 고르지 않는 경우(공집합)는 세지 않는다.

값이 같은 수가 여러 개 있어도 위치가 다르면 다른 수로 본다. 수가 1 1이고 $S = 1$이면 첫째 수만 고르는 경우와 둘째 수만 고르는 경우가 있으므로 답은 2이다.