<jupyter_start><jupyter_text>Chapter : BacktrackingTitle : Combination sum implementationLink : [YouTube](https://youtu.be/C6vZH6hnzJg)ChapterLink : 문제 : 주어진 array의 합이 sum이 되는 모든 combination 조합을 찾아라예제: [1,2,3] sum = 5답 : [[1,1,1,1,1],[1,1,1,2],[1,2,2],[1,1,3],[2,3]]<jupyter_code>from typing import List

class CombSum:
  def solution(self, in_list: List[int], target: int) -> List[List[int]]:
    if len(in_list)==0:
      return []

    #set init member Vars
    self.__result = []
    self.__in_list = in_list
    comb = []
    self.__bt(0,target,comb) #backtracking
    return self.__result


  def __bt(self, prevIdx:int, targetSum:int, comb:List[int]):
    #exit conditions
    if targetSum==0:
      self.__result.append(comb.copy())
    elif targetSum < 0:
      return
    
    #process(candidates filtering)
    for idx in range(prevIdx,len(self.__in_list)):
      num = self.__in_list[idx] 

      #recusion call
      comb.append(num)       
      self.__bt(idx,targetSum-num,comb)
      comb.pop()
    return

combSum = CombSum()
combSum.solution(in_list=[1,2,3],target=5)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.14618834080717488, 'fraction_numerical': 0.02780269058295964, 'mean_word_length': 3.7088607594936707, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 6, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '539783', 'license': 'MIT', 'n_tokens_mistral': 445, 'n_tokens_neox': 442, 'n_words': 78, 'path': 'backTracking/combSum.ipynb', 'repo_name': 'NoCodeProgram/CodingTest', 'size': '1115'}