조합

조합

: 서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것

 

조합의 수식

 

1. 반복문을 통한 조합 생성

# 0, 1, 2, 3, 4 중 3개의 숫자 조합 만들기
N = 5
for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            print(i, j, k)

'''
0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4
'''

 

2. 재귀 호출을 이용한 조합 생성

def nCr(n, r, s):
    if r == 0:
        print(*comb)
    else:
        # s -> 선택할 수 있는 구간의 시작
        # s부터 마지막 데이터 중 선택할거야
        for i in range(s, n-r+1):
            comb[r-1] = A[i]
            # 더 작은 단위의 조합을 구하러 가자,,
            nCr(n, r-1, i+1)

A = [0,1,2,3,4]
n = len(A)
r = 3
# 조합이 임시 저장될 배열
comb = [0] * r
nCr(n, r, 0)

'''
2 1 0
3 1 0
4 1 0
3 2 0
4 2 0
4 3 0
3 2 1
4 2 1
4 3 1
4 3 2
'''

 

 

 

연습문제 - 부분집합 합 문제 구현하기

 

설명

아래의 10개의 정수 집합에 대한 모든 부분 집합 중 원소의 합이 0이 되는 부분집합을 모두 출력하시오

arr = [-1, 3, -9, 6, 7, -6, 1, 5, 4, -2]
N = len(arr)
result = [-1] * N

def par(k):
    if k == N :
        sumV = 0
        # 특정 작업을 수행하는 부분,, 여기서는 프린트
        for i in range(N):
            if result[i] == 1:
                sumV += arr[i]
        if not sumV:
            for i in range(N):
                if result[i] == 1:
                    print(arr[i], end =' ')
            print()
        return

    for i in [0, 1]:
        result[k] = i
        par(k+1)

par(0)

>> 일단 풀긴 풀었으나,,sumV를 저렇게 밖에 확인할 수 없는지????? 냅다 포문쓰면 안될것 같은데 교수님께 여쭤보기