47)부분집합 구하기(DFS)

문제

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

 

조건

 

제한사항

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

 

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

 

단 공집합은 출력하지 않습니다.

 

문제풀이

def go(v):
  if v==N+1:
    for i in range(1, N+1):
      if ch[i]==1:
        print(i, end=' ')
    print()
  else:
    ch[v]=1
    go(v+1)
    ch[v]=0
    go(v+1)

N = int(input())
ch=[0]*(N+1)
go(1)