S2 1182. 부분수열의 합

문제 보기 :  1182번: 부분수열의 합

---

문제

• 정답률 : 43%

---

작성 코드

def combinations(n,new,c):
    answer = []
    if len(new)==n:
        return [new]
    for i in range(c,len(arr)):
        answer.extend(combinations(n,new+[arr[i]],i+1))
    return answer

n,goal = map(int,input().split())
arr = list(map(int,input().split()))
arr.sort()

visited = [False]*n
answer = []
for i in range(1,n+1):
    answer.extend(combinations(i,[],0))

ls = [1 for l in answer if sum(l)==goal]
print(sum(ls))

---

풀이

가장 포인트는 연속된 부분 수열이 아니라, 떨어져 있어도 부분수열로 인정이 된다는거.

 

그래서 처음 잘 못 이해했을 때는, 이중 for문으로 작성해 해결하려고 했으나 다른 사람의 예제에서

5 0

0 0 0 0 0 의 정답이 31이라는 것을 보고 다시 구현해야한다는 것을 깨달았다.

 

이 문제에서 n의 최대는 20이고, 시간 제한도 2초로 꽤 길어서 combinations를 사용해서 구현해도 괜찮겠다고 생각했고

def combinations를 먼저 정의한 다음, sum이 goal과 같은 조합들만 선별해 더했다.