양팔 저울 눈금 맞추기

문제

실험실의 양팔 저울로 눈금을 맞추는 실습을 합니다. 서로 구분되는 추가 n개 있고, weights[i]는 i번 추의 무게입니다.

각 추마다 정확히 세 가지 중 하나를 선택합니다.

• 왼쪽 접시에 올린다 → 무게만큼 +
• 오른쪽 접시에 올린다 → 무게만큼 -
• 올리지 않는다 → 0

이렇게 결정했을 때 (왼쪽 접시 무게 합) − (오른쪽 접시 무게 합)이 target이 되는 선택 방법의 가짓수를 반환하는 solution(weights, target) 함수를 작성하세요.

추는 무게가 같더라도 서로 다른 물건으로 구분합니다. 즉 어떤 추를 어느 접시에 올렸는지가 다르면 다른 방법으로 셉니다. 모든 추를 올리지 않는 선택도 하나의 방법입니다.

예시

예시 1 설명: 2번 추를 오른쪽, 3번 추를 왼쪽에 올린 -2 + 3 = 1 한 가지뿐입니다.

예시 2 설명: 두 개의 1을 각각 a, b라고 하면 다음 네 가지입니다.

• +a −b +2, −a +b +2, a·b 모두 미사용 +2, +a +b(2는 미사용)

예시 3 설명: 추를 올리지 않으면 차이가 0이므로 한 가지입니다.

제약 조건

• 1 ≤ weights.length ≤ 14
• 1 ≤ weights[i] ≤ 100 (정수)
• -1,000 ≤ target ≤ 1,000 (정수)

시간 복잡도 목표: O(3^n)

공간 복잡도 목표: O(n)