문제 링크

https://leetcode.com/problems/combination-sum/

문제 정리

• 숫자 집합 candidates를 조합하여 합이 target이 되는 원소 나열. 각 원소 중복 사용 가능

• 입력값 candidates

  candidiate = [2, 3, 6, 7]
  

• 입력값 target

  target = 7
  

• 출력값

  [
  	[7],
  	[2, 2, 3]
  ]
  

접근 방법

• dfs에서 풀어보았던 조합이란 문제와 비슷하게 접근해보았다. 차이점은 중복값의 사용 여부이다.

• 알고리즘은 target에서 각 요소들을 하나씩 더해서 누적값을 빼나가는 방식이다.

• 종료조건으로는 누적값인 comb를 만들어 0보다 작을 경우 종료조건1로 지정하고 comb가 0일경우에는 정답이므로 추가해준다.

  

코드 진행

1. dfs함수에 최초값을 넣어 실행시킨다.

   dfs(comb=target, index=0, path=[])
   

2. dfs함수 생성

   1. 첫번재 종료조건 comb가 0보다 작아질때

      def dfs(comb, index, path):
              # (1) 종료조건 - 0보다 작아질때
              if comb < 0:
                  return
      

   2. 두번째 종료조건 comb=0으로 정답처리

      # (2) 종료조건 - 0일때 결과값에 추가.
              if comb == 0:
                  result.append(path)
                  return
      

   3. 재귀방식으로 처리

      # 반복문 시작
              for i in range(index, len(candidates)):
                  # comb에 target에서 빼나간다. path에는 값 누적
                  dfs(comb - candidates[i], i, path + [candidates[i]])
      

      재귀가 작동하는 방식.