재귀(recursion): 부분집합의 합, 순열

배열에 재귀로 접근하려면,

① 현재 접근하려는 인덱스, ② 배열의 크기 정보가 필요하다!

※ 참고: 일반적으로 재귀에서는 인덱스와 배열의 크기가 일치할 때($ i==N $)를 재귀 종료 조건으로 만들면 된다.

---

1. 부분집합의 합

## 1번 ##
def f(i, N, K): # 합이 K인 부분집합을 출력 (i: 위치, N: 배열의 크기, K: 구하고자 하는 합)
    if i==N: # 부분집합 생성완료
        s = 0
        for j in range(N):	# 완성된 부분집합의 합 구하기
            if bit[j]==1:
                s += A[j]
        if s == K: # 합이 찾는 값이면
            print(bit, end= ' ')
            for j in range(N):
                if bit[j]==1:
                    print(A[j], end =' ')  # 부분 집합 출력
            print()
    else:	# 부분집합 생성 미완료
    	# 양쪽을 모두 가봐야 하므로 재귀호출 2개
        bit[i] = 1	# i) 넣거나
        f(i+1, N, K)
        bit[i] = 0	# ii) 말거나
        f(i+1, N, K)

## 2번 ##
def f2(i, N, K, S, RS):	# S: 중간합, RS: 남은 원소들의 합
    if S==K:	# 부분집합의 합이 구하고자 하는 값이면, 완료
        print(bit, end=' ')
        for j in range(N):
            if bit[j] == 1:
                print(A[j], end=' ')  # 부분 집합 출력
        print()
    elif i==N:	# 합이 K 값이 아닌데 이미 고려할 요소가 동남: 종료
        return
    elif S > K:	# 이미 구할 K 값을 초과함: 종료
        return
    elif S+RS < K:	# 앞에서 요소를 너무 많이 배제해서, 뒤에 있는 요소를 모두 포함해도 K 값 미만일 때: 종료
        return
    else:
        bit[i] = 1
        f2(i + 1, N, K, S+A[i], RS-A[i])
        bit[i] = 0
        f2(i + 1, N, K, S, RS-A[i])	# A[i] 포함하지 않아도 고려된 요소이니 RS에서 -A[i] 해줘야 함

A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
bit = [0]*10
f(0, 10, 10)
f2(0, 10, 25, 0, sum(A))

 

2. 순열(permutation)

def f(i, N): # P[i]의 값을 결정
    if i == N:  # 순열 만들기 완료
    	print(P)
    else:
        for j in range(i, N): # P[i] <-> P[j] 자리교환
            P[i], P[j] = P[j], P[i]
            f(i+1, N)
            P[i], P[j] = P[j], P[i]
        return
  
P = [1,2,3]
f(0, 3)

위 예시에서, i=2 인 상태에서 호출된 함수 $ f(3, N) $ 은 결과값을 return하면 i=2인 곳으로 돌아가고, 또 i=1인 곳으로 돌아가는 것이다! (※ return문에 반환할 객체를 명시하지 않으면 None 객체를 반환한다.)

for문이 끝나면 해당 함수를 호출한 상위 함수로 돌아가는 것. 즉, 끝나니까 전 단계로 돌아가는 것!!