[leetcode][39] Combination Sum

문제 : leetcode.com/problems/combination-sum/

---

정수형 배열 candidates이 주어질 때 이들을 더해서 target을 만들 수 있는 배열을 구해라.

이 때, candidates 값은 중복해서 더해질 수 있다.

---

오랜만에 찾아온 백트래킹 친구.

fun backtracking(index, target, 저장배열[]) {
  if (target == 0) 정답배열에 저장배열 추가.
  if (target < 0) 정답 불가능하므로 종료.
  for(num = candidates[index, 끝]) { 
     저장배열 뒤에 num 추가.
     backtracking(index, target - num, 저장배열)
     저장배열 뒤에 추가한 num 삭제.
  }
}

 

시간복잡도는 O(|candidates| * target).

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/39.%20Combination%20Sum.cpp