부분집합 구하기(DFS)

부분집합 구하기(DFS)

자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하세요.

 

▣ 입력설명

첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.

 

▣ 출력설명

첫 번째 줄부터 각 줄에 하나씩 부분집합을 아래와 출력예제와 같은 순서로 출력한다.
단 공집합은 출력하지 않습니다.

 

▣ 입력예제 1

3

 

▣ 출력예제 1

1 2 3
1 2
1 3
1
2 3
2
3

---

풀이

DFS를 이용한다.

체크변수 ch를 만들어 사용하는 원소에는 1을, 사용하지 않는 원소에는 0을 넣어준다.

 

주의

v=4 가 되고 1,2,3 이 출력되고 난 후

v=3 인 상태로 ch[v]=0 으로 넘어오므로 1,2 가 출력된다.

 

---

코드

def DFS(v):
    if v==n+1: # 종착점
        for i in range(1,n+1):
            if ch[i]==1: # 체크 변수의 인덱스가 체크되는 것이므로
                print(i, end=' ') # i를 출력해준다.
        print() # 줄바꿈
    else: 
        ch[v]=1 # 원소를 부분집합으로 사용하겠다. 체크
        DFS(v+1) # 1, 2, 3 순으로 넣어가며 사용할지말지
        ch[v]=0 # 원소를 부분집합으로 사용하지 않겠다.
        DFS(v+1)


if __name__=="__main__":
    n = int(input())
    ch = [0]*(n+1) # 체크 변수
    DFS(1)