모든 경우를 탐색하는 재귀 함수를 만든다.
형태는 func(position, sum) 과 같은 형태로 만들었다. "배열의 현재 position까지로 합이 sum이 되었을 때로 만들어 지는 경우의 수" 이다.
계속 2가지로 갈래를 뻗어나가면서 position이 N-1이 되는 순간 a[N-1] 과 같은 경우만 경우의 수로 세면 된다.
N이 꽤 크다보니 이대로는 $O(2^N)$ 이기 때문에 무조건 재귀는 힘들고, 메모이제이션을 적용하면 충분히 시간내에 정답을 받을 수 있다.
첫 숫자가 "무조건 선택"임을 무시해서 여러 번 틀렸다. 항상 조건에 조심해야겠다.
댓글 없음:
댓글 쓰기