[LV1] 2개 뽑아서 더하기 Python

https://programmers.co.kr/learn/courses/30/lessons/68644

코딩테스트 연습 - 두 개 뽑아서 더하기

해당 문제는 조합 만드는 방법을 사용해서 해결하였다.

2중 for문으로 간단하게 해결할 수도 있지만.

조합 만드는 방법을 해당 풀이로 학습해보자.

 

다양하게 응용할 수 있다.

 

def solution(number):
    # 결과가 중복이 가능하므로 set으로 선언한다.
    answer = set()
    # 조합을 만들 stack을 선언한다.
    stack = []

    def check(next_idx):
        if len(stack) == 2:
            answer.add(sum(stack))
            return
        for i in range(next_idx, len(number)):
            stack.append(number[i])
            check(i + 1)
            stack.pop()

    for i in range(len(number)):
        # 해당 숫자를 사용해서 조합을 만든다.
        stack.append(number[i])
        # 다음 숫자들 여부를 재귀로 결정한다.
        check(i + 1)
        # 해당 숫자를 제거하여 사용하지 않는다.
        stack.pop()
    return sorted(list(answer))

 

len이 4 면 1234... 1235 1245

len이 2면 12 13 14 23 24 34

 

위와 같이 조합을 만들어낸다.

 

문제 풀이에 매우 다양하게 응용 가능한 재귀 구현이니 배워두자.