Combination Sum - Back Tracking (Python)

Recursive는 컨디션 좋을 때 봐도 잘 모르겠다.

 

솔직히 완벽한 논리적 이해보단

 

이렇게 하면 되겠거니.. 하면서 느낌적으로 접근하는 경우가 많다.

 

답안을 봐도 헷갈리는데, 시험장에서 만나면 오죽하랴..

 

Recursive문제를 맘 먹고 꼬아서 내면 답이 없을 거 같다.

Q6.ipynb

0.00MB

 

6. Combination Sum [7 pt]

Given an array of distinct integers numbers and a target integer target, write a function combination_sum(numbers, target) to find all unique combinations in numbers where the candidate numbers sum to target. The same number from numbers can be used multiple times in the combination. Return a list of all unique combinations.

• Requirements
  • Output must be a list of lists, each sub-list containing an unique combination of numbers with duplicates allowed (i.e. [2,2,2] for making 8).
  • If no such combination exists, return an empty list
• Hint
  • It may be useful to utilize an auxiliary function count_sums(), for which we have given the header, as your recursive function that can take the current state of the problem (such as the remaining target sum, the current combination being built, and the starting index for candidates) and recursively explore all possible combinations.
  • The use of the auxiliary function count_sum() is optional and not implementing this function will not result in any penalization.
    • If you do not decide to use the auxiliary function, please comment out the function declaration.
  • You are also allowed to use the internal sorted() function that sorts a given list for checking duplicate combinations
• Example

  numbers = [2, 3, 6, 7]
  target = 7
  print(combination_sum(numbers, target))  # Expected output: "[[2, 2, 3], [7]]"
  

  numbers = [2]
  target = 8
  print(combination_sum(numbers, target))  # Expected output: "[[2, 2, 2, 2]]"

def combination_sum(numbers, target): #input은 전부 양수라고 가정
    if not numbers : return []
    result = []
    count_sums(0,target,[],result)
    return result

def count_sums(start,target,current,result):
    if target == 0 :
        result.append(list(current)) 
# result.append(current) 를 하면 current의 주소를 참조해서 더함
# -> current가 나중에 바뀌면 result에 더해진 것도 바뀜
        return
    if target < 0 :
        return
    
    for i in range(start,len(numbers)):
        current.append(numbers[i])
        count_sums(i,target-numbers[i],current,result)
        current.pop()

 

참고로 Recursion으로 징징거리기 싫으면 Stack 구조를 써도 된다.

 

by GPT

 

def combination_sum(numbers, target):
    results = []
    stack = [(0, [], target)]  # (start index, current combination, remaining target)

    while stack:
        start, current_combination, current_target = stack.pop()

        if current_target == 0:
            results.append(current_combination)
            continue
        if current_target < 0:
            continue

        for i in range(start, len(numbers)):
            new_combination = current_combination + [numbers[i]]
            new_target = current_target - numbers[i]
            stack.append((i, new_combination, new_target))

    return results

# 테스트 코드
numbers = [2, 3, 6, 7]
target = 7
print(combination_sum(numbers, target))  # Expected output: [[2, 2, 3], [7]]
numbers = [2]
target = 8
print(combination_sum(numbers, target))  # Expected output: [[2, 2, 2, 2]]