알고리즘
[C++] Boj 1182 부분수열의 합
문제 링크1182 부분수열의 합 접근모든 경우의 수를 확인하는 백트래킹 문제이다. N개의 정수로 이루어진 수열이 있을 때, 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성해야 한다. 이때, 중요한 점은 크기가 양수인 부분 수열 중에서 경우의 수를 구해야 한다는 것이다. 이 말은, 공집합은 포함하지 않는다는 말이다. 이 문제는 중학교 때 배웠던 부분 집합 구하기 경우의 수 문제를 떠올려 쉽게 해결할 수 있다.만약 n1, n2, n3의 수 중 부분 수열을 만들어 합 S를 만들어야 한다면, n1을 선택하고, 안 하고, n2를 선택하고, 안 하고를 반복해서 선택한 숫자들의 합이 S가 되게 만들면 된다. 이때 주의해야 할 점은 S가 1 이상인 경우는 상관없으나 S가 0일 때 아무..
