[백준 알고리즘] 2309.일곱난쟁이 - 부분집합의 합(조합)

 

 

 

 

 

 

부분집합의 합이 100이 되도록 하면 되는 문제이다.

 

 

 

재귀를 사용해 풀었고, 만족하는 조건을 한번만 출력하면 되기에 flag 변수를 사용했다.

 

만족하는 경우 이후 재귀에서 바로 return 하도록 만들어 함수를 끝냈다.

 

 

 

 

#### 부분집합의 합 -> 조합

def subset(idx ,cur_sum, start):
    global flag
    if flag == 1: return
    if idx == 7:
        if cur_sum == 100:
            flag = 1
            select.sort()
            for i in select:
                print(i)
            return 1
        return
    for i in range(start, 9):
        select.append(dwarfs[i])
        subset(idx+1, cur_sum+dwarfs[i], i+1)
        select.pop()

select = []
dwarfs = []
flag = 0
for i in range(9):
    dwarfs.append(int(input()))



subset(0, 0, 0)