DFS 연습 - 양팔저울과 추

추들이 주어졌을 때,  "1~ 가능한 최대무게(추들 총합)" 사이의 정수 중에서 양팔저울로 잴 수 없는 무게 구하기 문제

1. 손으로 정리

2. 잘못 풀었던 1차시도 (이렇게 하면 양팔저울의 의미 전혀 없구 그냥 부분집합 구하는 거나 다름이 없다..!)

def DFS(L, weight):
    if L == len(nums):
        possible_set.add(weight)
        return
    else:
        DFS(L+1, weight)
        weight += nums[L]
        DFS(L+1, weight)


if __name__ == "__main__":

    nums = [ 1, 5, 7 ]
    S = 13
    possible_set = set()
    result_list = []
    DFS(0, 0)

    for i in range(1, S+1):
        if i not in possible_set:
            result_list.append(i)

    print(result_list)

3. 2차 시도

def DFS(L, weight):
    if L == len(nums):
        if weight >= 1:
            possible_set.add(weight)
        return
    else:
        weight -= nums[L]
        DFS(L+1, weight)
        weight += nums[L]
        DFS(L+1, weight)
        weight += nums[L]
        DFS(L+1, weight)


if __name__ == "__main__":

    nums = [ 1, 5, 7 ]
    S = 13
    possible_set = set()
    result_list = []
    DFS(0, 0)

    for i in range(1, S+1):
        if i not in possible_set:
            result_list.append(i)


    print(result_list)  # 출력 >> [9, 10]

4. (나중에..?) 다시 생각해보기ㅎㅎ

- 양팔저울이다보니 분명 대칭의 결과가 나올 건데, 그런 경우를 edge point로 잡아내서 연산 굳이 안하는 방법은?!