[python] 부분집합 구하기(DFS)

[문제]

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

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

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

▣ 입력예제 1
3
▣ 출력예제 1
1 2 3
1 2
1 3
1
2 3
2
3

---

[코드]

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)


n = int(input())
ch = [0] * (n+1)    # 집합의 사용 여부를 체크하기 위한 체크 변수

dfs(1)

---

[내용]

** 전혀 접근 조차 하지 못했다.

 

- 백트래킹: 모든 경우의 수를 고려하는 알고리즘. 모든 가능한 케이스가 나열된 상태공간트리를 작성해서 문제를 푼다.
- 백트래킹 종류: dfs, bfs
1) dfs: 모든 경우의 수를 구할 경우
2) bfs: 최단 거리 구할 경우