[Array] Combination Sum

 

candidates 배열과  target 숫자가 주어질 때, candidtates 배열의 부분집합 원소합이 target이 되는 부분집합들을 배열로 다시 만들어 리턴하는 문제이다.

단, candidates의 원소는 중복해서 여러번 사용할 수 있다.

 

구체적으로 설명하기 위해 콘솔을 찍었다.

subset, sum, index를 args로 가진 search 라는 함수를 재귀로 사용한다.

이때 subset은 true라면 리턴배열에 넣을 부분합, sum은 target과 같은 값을 가지는지 여부 확인을 위한 원소의 합, index는 검사를 위한 요소를 가리키는 숫자이다.

 

실제 콘솔값을 보면 가능한 조합에 대해 모두 검사함을 알 수 있다.

로직을 돌리기 전 오름차순으로 정렬하고 element마다 하나씩 검사한다.

각 element에 대해 subset의 모든 원소의 합인 sum이 target 값과 같은 경우만 answer에 넣는다.

이때 subset의 합이 target값보다 작으면, 재귀를 이용해 element만 추가하여 다시 검사하고, target값보다 크면 검사를 종료한다.