[알고리즘] 되추적 - 부분집합의 합 코드 (Back_Tracking - Sum_Of_Subsets Code)

문제)

Description

교재와 강의자료를 참고하여 Sum-of-Subsets 문제를 푸는 Algorithm 5.4의 구현을 완성하시오.

n개의 원소를 가진 정수의 집합 S가 주어지고,

임의의 정수 W가 주어졌을 때,

합이 W가 되는 부분집합의 개수와 각 부분집합을 출력하도록 하시오.

Input

첫 줄에 원소의 개수 n과 임의의 정수 W가 주어진다.

둘째 줄에 n개의 정수가 주어진다.

Output

첫 줄에 원소의 합이 W가 되는 부분집합의 개수를 출력한다.

둘째 줄부터 원소의 합이 W가 되는 모든 부분집합을 한 줄에 하나씩 출력한다.

단, 부분집합에서의 원소 출력 순서는 주어진 S의 원소 순서와 동일해야 한다. (백트래킹 순서대로)

Sample Input 1

4 13
3 4 5 6

Sample Output 1

1
3 4 6

Sample Input 2

3 10
1 2 3

Sample Output 2

0

Sample Input 3

20 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Sample Output 3

64
1 2 3 4 10
1 2 3 5 9
1 2 3 6 8
1 2 3 14
1 2 4 5 8
1 2 4 6 7
1 2 4 13
1 2 5 12
1 2 6 11
1 2 7 10
1 2 8 9
1 2 17
1 3 4 5 7
1 3 4 12
1 3 5 11
1 3 6 10
1 3 7 9
1 3 16
1 4 5 10
1 4 6 9
1 4 7 8
1 4 15
1 5 6 8
1 5 14
1 6 13
1 7 12
1 8 11
1 9 10
1 19
2 3 4 5 6
2 3 4 11
2 3 5 10
2 3 6 9
2 3 7 8
2 3 15
2 4 5 9
2 4 6 8
2 4 14
2 5 6 7
2 5 13
2 6 12
2 7 11
2 8 10
2 18
3 4 5 8
3 4 6 7
3 4 13
3 5 12
3 6 11
3 7 10
3 8 9
3 17
4 5 11
4 6 10
4 7 9
4 16
5 6 9
5 7 8
5 15
6 14
7 13
8 12
9 11
20

코드)

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


def sum_of_subsets(i: int, weight: int, total: int) -> None:
    global cnt
    global subset
    if promising(i, weight, total):
        if weight == W:
            cnt += 1
            for j in range(1, i + 1):
                if subset[j]:
                    subset_set.append(f'{S[j]} ')
            temp = subset_set.pop()[:-1]
            temp = temp + '\n'
            subset_set.append(temp)

        else:
            subset[i + 1] = 1
            sum_of_subsets(i + 1, weight + S[i + 1], total - S[i + 1])
            subset[i + 1] = 0
            sum_of_subsets(i + 1, weight, total - S[i + 1])


if __name__== "__main__":
    n, W = map(int, input().split())
    S = [0] + list(map(int, input().split()))
    total = sum(S)

    cnt = 0

    subset = [0] * (n + 1)
    subset_set = []

    sum_of_subsets(0, 0, total)

    print(cnt)

    for i in subset_set:
        print(i, end='')

 

2번째 코드)

def promising(i: int, weight: int, total: int) -> bool:
    # 유망함의 조건은 총 2가지
    # 현재 무게에 남은 모든 무게를 더했을 때 W보다 크거나 같아야 한다. 작으면 다 채워도 W에 미치지 못한다는 의미 => weight + total >= W
    # 현재 무게에 다음 물건의 무게를 더했을 때 W보다 작거나 같아야 한다. => weight + S[i + 1] <= W
    # 따라서 W는 다음 물건의 무게를 더한 것 보다 크고, 전체를 합한 것보다 작아야 한다.

    return weight + S[i + 1] <= W <= weight + total
    # return weight + total >= W >= weight + S[i + 1]
    # 이때 S[i + 1]를 먼저 참조 하는 코드는 사용 x, 사용하고 싶다면 S의 마지막에 0을 추가할 것


def sum_of_subsets(i: int, weight: int, total: int) -> None:
    global subset
    if weight == W:
        # 만약 현재 무게가 목표 무게와 같다면
        global cnt
        cnt += 1        # 카운트를 1 증가
        temp = [S[j] for j in range(1, i + 1) if subset[j]]     # subset[?]가 1인 숫자에 해당 하는 위치에 있는 S[?]를 넣음 ...
        subset_set.append(temp)     # temp를 추가함
        
    elif promising(i, weight, total):
        # 만약 현재 무게와 목표 무게가 같지 않다면 유망함을 체크함
        subset[i + 1] = 1       # 다음 물건을 넣음
        sum_of_subsets(i + 1, weight + S[i + 1], total - S[i + 1])      # 물건을 넣었을 때
        subset[i + 1] = 0       # 다음 물건을 넣지 않음
        sum_of_subsets(i + 1, weight, total - S[i + 1])     # 물건을 넣지 않았을 때


if __name__== "__main__":
    n, W = map(int, input().split())        # 개수와 합
    S = [0] + list(map(int, input().split())) + [0]      # 집합
    total = sum(S)      # 집합의 합

    cnt = 0     # 부분 집합의 개수
    subset = [0] * (n + 1)      # 중간중간 넣을지 말지 고민하는 상태 공간의 집합
    subset_set = []     # 제대로 된 sequence의 집합임

    sum_of_subsets(0, 0, total)

    # 아래는 출력
    print(cnt)

    for i in subset_set:
        print(*i, sep=' ')