210516 Back tracking - sum of subsets

학교 과제로 푼 문제 

 

원소들의 합이 특정 수가 되는 부분집합을 모두 구하는 문제

 

예를들어 {1,2,3,4} 의 부분집합 중 합이 5가 되는 부분집합을 찾는 문제이다. 

 

답은 {1,4} {2,3}이 될것이다.. 

 

원소를 정렬하고 맨 앞에서부터 넣는다/안넣는다 2개로 분기해나가는 트리를 만들되, 

 

트리를 다 그려보는 것이 아니라 가능성이 없으면(이미 무게를 넘었거나 남은거 다더해도 모자랄 때) 진행을 멈춘다. 

 

별로 어려운 문제는 아니라서 낼 걍 몰아서해도 될거같지만 조금이라도 코딩하고자려고 풀었음 

 

열심히 노느라고 안드공부 하나도 안한 주말......

 

평소에 잘 안하지만 오늘은 코드 첨부해봐야지 쓸내용이없으니껭 

 

출력형식이 별로 맘에안드는데 내일 바꿔서 낼것이다...ㅋㅋㅋ

 

 

n = 4
w = [1,4,2,6]
w.sort()
W = 6
print("items =", w, "W =", W)
include = n* [0]
total = 0
for k in w:
    total += k

def promising(i, weight, total):
    return (weight + total >= W) and (weight == W or weight + w[i + 1] <= W)


def s_s(i, weight, total, include):
    if promising(i, weight, total):
        if weight == W:
            print(include[:i+1])
        else:
            include[i + 1] = "yes"
            s_s(i + 1, weight + w[i + 1], total - w[i + 1], include)
            include[i + 1] = "no"
            s_s(i + 1, weight, total - w[i + 1], include)





s_s(-1, 0, total, include)