본문 바로가기

알고리즘

부분 수열의 합

Basic 100 · 99번Lv. 2완전 탐색

부분 수열의 합

문제 설명

자연수로 이루어진 수열 nums와 목표 값 target이 주어집니다. nums에서 부분 수열을 선택하여 그 합이 target과 일치하는 경우의 수를 반환하는 함수를 작성해주세요. 부분 수열은 수열에서 순서를 유지하면서 일부 원소를 선택한 것을 의미합니다.


제한 사항

  • nums의 길이는 1 이상 20 이하입니다.
  • nums의 원소는 1 이상 50 이하의 자연수입니다.
  • target은 1 이상 1000 이하의 자연수입니다.
  • 연습 안내: 백트래킹으로 풀어 보세요. 채점은 반환한 결과만 확인합니다.
  • 입력 data의 첫 번째 값이 nums, 두 번째 값이 target입니다.
  • 값이 같아도 위치가 다른 원소를 고르면 다른 부분 수열로 셉니다.

입출력 예

numstarget반환값
[1, 2, 3, 4, 5]73
[1, 2, 3, 4, 5]103
[1, 2, 3, 4, 5]151
[1, 2, 3, 4, 5]200
[3, 5, 7, 9]122

입출력 설명

  • 첫 번째 예시에서 [1, 2, 3, 4, 5]의 부분 수열 중 합이 7인 경우는 [2, 5], [3, 4], [1, 2, 4]로 3가지입니다.
  • 두 번째 예시에서 [1, 2, 3, 4, 5]의 부분 수열 중 합이 10인 경우는 [1, 2, 3, 4], [1, 4, 5], [2, 3, 5]로 3가지입니다.
  • 세 번째 예시에서 [1, 2, 3, 4, 5]의 부분 수열 중 합이 15인 경우는 [1, 2, 3, 4, 5]로 1가지입니다.
  • 네 번째 예시에서 [1, 2, 3, 4, 5]의 부분 수열 중 합이 20인 경우는 없습니다.
  • 다섯 번째 예시에서 [3, 5, 7, 9]의 부분 수열 중 합이 12인 경우는 [3, 9], [5, 7]로 2가지입니다.

예시 테스트

#입력기대값
1[[1, 2, 3, 4, 5], 7]3
2[[1, 2, 3, 4, 5], 10]3
3[[1, 2, 3, 4, 5], 15]1

입력은 solution에 넘기는 인자예요. 제출하면 숨김 테스트 8개도 함께 채점해요.