재귀함수로 부분집합 만들기...

# 재귀함수로 부분집합 만들기
# bits: 해당 인덱스의 요소를 사용할지의 유무 (1은 사용하고 0은 아님)
# depth : 내가 얼마나 함수를 재귀호출했는지에 대한 카운트 값...
def recur(bits, depth):
    # 기저 조건
    if depth == N:
        for i in range(N):
            if bits[i] == 1:
                print(arr[i], end=' ')
        print()
        return

    for i in range(2): # 0, 1
        bits[depth] = i
        # 자기 자신을 호출
        recur(bits, depth + 1)


N = 4
arr = [1, 2, 3, 4]
recur([0] * N, 0)

# result
4 
3 
3 4 
2 
2 4 
2 3 
2 3 4 
1 
1 4 
1 3 
1 3 4 
1 2 
1 2 4 
1 2 3 
1 2 3 4

뒤에서 하나하나 돌아온다고 생각해주면 이해하기 쉬울것 같다~~~

 

재귀함수 너무 어려워요오....제제제.....기.........랄,,,,

 

여기서 제일 중요한 포인트는 [0, 0, 0, 0] 배열을 끝까지 만들어주고 역으로 만들어져 나가는 느낌이라는거?

return을 받았을 때, 제일 처음이 아닌 자신을 호출했던 곳으로 돌아가 0이 아니라 1인 경우를 만들어준다는거??

그래서 답을 출력했을때, 리스트에 가장 먼저 저장된 1이 아니라 4가 나오는 부분이 정말 중요 포인트인거 같다...

 

재귀의 가장 대표적인 예 : 팩토리얼