backtracking 1

문제는 더블릿 25 backtracking에 있는 scales입니다.

문제 사이트 주소입니다.

http://183.106.113.109/30stair/scales/scales.php?pname=scales

입력받은 무게들의 합이 반이 되는 부분집합의 수를 구하는 문제입니다.

이를 구하기 위해선 예제인 1 9 5 3 8로 볼 경우

1

1 9

1 9 5

1 9 5 3 8

1 5

1 5 3

등 모든 경우의 수를 봐야합니다.

이럴 때 백트래킹을 쓰는데 재귀를 사용합니다.

우선 1 9 5 3 8을 배열에 입력 받고 재귀를 호출하는 방식은 다음과 같습니다.

현재 값으로 그냥 호출, 현재값에 다음값을 더해 호출

두 경우 모두 각각 카운터값을 1씩 증가시킵니다.

그럼 첫 번째 값 1에 대해 다음 호출은 1과 1+9가 됩니다.

그 다음 호출은 

1에서 파생한 1과 1+5, 그리고 1+9에서 파생한 1+9와 1+9+5가 되는 것이죠.

이런식으로 모든 경우의 수를 구해주면서 재귀를 끝낼 조건을 지정해줘야합니다.

문제에서는 이 합이 전체합의 반이 되는 경우를 물어보고 있으므로 이 경우에 위에서 말한것과 다른 별도의 카운터를 선언해서 값을 증가시킵니다.

그리고 호출 시마다 증가시키는 카운터는 배열의 인덱스를 넘어갔을 경우 조건식을 판별하기 위해 사용하고, 속도를 빠르게 하기 위해 호출시마다 해주는 합이 전체 합의 반보다 큰 경우에는 다음 호출을 하지 않도록 합니다.