[인프런] 부분집합 구하기

---

문제설명

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

입력조건

• 첫 줄에 자연수 N(1 <= N <=10)이 주어진다.

출력조건

• 첫 줄부터 각 주렝 하나씩 부분집합을 아래의 출력예제와 같은 순서로 출력한다. 단, 공집합은 출력하지 않는다.

입력 예제 : 1 

출력 예제 :

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

사고과정

• 상태트리를 만들었을 때, 해당 원소를 사용했는지 안했는지를 참조하는 것을 어떻게 구현해야 할지 몰랐다..
• 풀이를 보니 사용 여부를 기록하는 일종의 '방문 여부' 기록 리스트를 새롭게 정의해서 구현해야 한다. 예전의 DFS 문제들이 왜 이런 변수를 이러한 이유 때문에 선언했다는 걸 이제야 확 체감한 듯 하다.. DFS를 잘 풀려면 상태트리를 잘 만들줄아야 한다고 한다. 그래서 이를 많이 연습해야겠다!
• 아직은 DFS가 너무 어렵..

풀이(스스로 못 푼 풀이)

def DFS(x):
    if x > n:
        for i in range(1, n+1):
            if check[i] == 1:
                print(i, end=' ')
        print()
        return
    check[x] = 1  # 사용!
    DFS(x+1)
    check[x] = 0  # 미사용!
    DFS(x+1)

n = int(input())
# 방문했는지 용 체크 테이블 하나 정의해야 함! -> 이것이 곧 해당 원소를 사용할지 안할지를 정하는 기반이 됨!
check = [0] * (n+1)
DFS(1)