[python] 재귀함수

재귀로 집합 A의 부분집합 만들기

A, B, C 가 음식점을 갈 수도 있고, 안 갈 수도 있다. 그렇지만 모두 안가진 않는다. 이런 경우의 수는?
●  A = [1, 2, 3] : 
●  b = i번 원소의 포함 여부를 나타냄

A : 부분 집합을 구성하는 요소들을 담고 있는 원본 배열

b :  부분 집합의 구성 요소를 표시하기 위한 플래그 배열, 원본 배열 A의 각 요소에 대한 포함 여부(0은 해당 요소를 포함하지 않음, 1은 해당 요소를 포함)

 

def f(k, n):
    if n==k: # b배열을 벗어나면
        for i in range(n):
            if b[i] == 1:
                print(A[i], end='')
        print()
    else:
        b[k]=0
        f(k+1, n)
        b[k]=1
        f(k+1, n)

A = [1, 2, 3]
b = [0, 0, 0]
f(0, 3)

---

코드 해석

def f(k, n):: 재귀 함수 f를 정의합니다. k는 현재 인덱스를 의미하고, n은 배열 A의 길이를 나타냅니다.
if n == k:: 현재 인덱스 k가 배열 A의 길이 n과 동일하면, 부분 집합을 출력합니다.
for i in range(n):: 부분 집합을 구성하는 요소들을 확인하기 위해 배열 A의 모든 요소에 대해 반복합니다.
if b[i] == 1:: b 배열의 i 인덱스 값이 1이면, 해당 요소를 부분 집합에 포함시킵니다.
print(A[i], end=''): 현재 포함된 요소를 출력합니다.
print(): 부분 집합을 출력한 후 줄바꿈합니다.
else:: 현재 인덱스 k가 배열 A의 길이 n과 동일하지 않으면, 재귀적으로 부분 집합을 구성합니다.
b[k] = 0: 현재 인덱스 k에 해당하는 요소를 부분 집합에 포함시키지 않는 경우를 나타내기 위해 b[k] 값을 0으로 설정합니다.
f(k+1, n): 다음 인덱스로 재귀 호출합니다.
b[k] = 1: 현재 인덱스 k에 해당하는 요소를 부분 집합에 포함시키는 경우를 나타내기 위해 b[k] 값을 1으로 설정합니다.
f(k+1, n): 다음 인덱스로 재귀 호출합니다.