부분집합 구하기(DFS)

못풀겠어서..
hint: 1 2 3 이 있다면
먼저 1을 넣을건지? 넣지 않을건지 >>
다음으로 2를 넣을건지? 넣지 않을건지 >>
다음으로 3를 넣을건지? 넣지 않을건지 >>
...
진행시킨다

2 2 2 -1 (공집합 빼면)
경우의 수 7가지 이다.

...............................D(1)...............................
.......................................................................
...........1넣음D(2).............1안넣음D(2).......
.......................................................................
2넣음D(3)..D(3)2안넣음....2넣음D(3)..D(3)2안넣음

이런식으로 트리를 생각해 보아라 !!!
이런트리를 상태트리라고 한다 !!

상태트리

import sys
sys.stdin = open("input.txt", "rt")

def DFS(v):
    if v == n+1:
        for i in range(1,n+1):
            if ch[i]==1:
                print(i, end=' ')
        print()

    else:
        ch[v]=1
        DFS(v+1)
        ch[v]=0
        DFS(v+1)

if __name__ == "__main__":
    n =int(input())
    ch=[0]*(n+1)
    DFS(1)