BOJ 1182
BOJ 1182 부분수열의 합 [Java]
BOJ 1182 부분수열의 합 1. 문제 링크 https://www.acmicpc.net/problem/1182 2. 문제 해설 재귀를 이용해서 풀었다. 각 원소마다 더할 것인지 더하지 않을 것인지를 선택할 수 있고 그에 따라 재귀 함수가 계속 호출된다. 그러므로 시간복잡도는 O(2^n)이다. 최악의 경우에 n이 20이기에 주어진 시간 안에 충분히 해결할 수 있다. 재귀 함수의 매개 변수로 idx와 sum을 주어 현재 몇번째 idx에 위치해있고, 더한 값이 얼마인지를 담았다. 재귀 함수의 탈출 조건은 idx가 n과 같아지면 탈출하고, 만약 sum이 s와 일치하면 경우의 수 값 cnt를 +1 해준다. 문제 조건에서 부분수열의 크기가 양수여야하는 조건이 있으므로 만약 s가 0이라면 아무 것도 더해주지 않은 ..