Go - 부분집합 (MS 인터뷰 문제: DFS 완전탐색)

 

package main

import "fmt"

var n int
var ch [11]int

func solution(L int) {
	if L == n + 1 {
		for i := 1; i<=n; i++ {
			if ch[i] == 1 {
				fmt.Printf("%d ", i)
			}
		}
		fmt.Println()
	} else {
		ch[L] = 1
		solution(L + 1)
		ch[L] = 0
		solution(L + 1)
	}
}

func main() {
	fmt.Scanln(&n)
	solution(1)
}

 

 

이문제를 해결하기위해 dfs 방식으로 풀었습니다

solution 의 인자 L 을 노드의 깊이로 정했습니다. n 이 3으로 입력 받아 졌을때  노드의 깊이가 n + 1 과 똑같을 때 멈춘뒤 ch 체크 배열에 1로 체크 된 인덱스 값을 출력합니다.

 

ch[L] = 1
solution(L + 1)
ch[L] = 0
solution(L + 1)

 

자식 노드가 왼쪽으로 뻗어 나갈때는 1 오른쪽으로 뻗어 나갈때는 0 if 문에 걸렸을 때 배열을 출력합니다.

 

1 에서 왼쪽 자식 2로 갈때 [0, 1, 0, 0,....] 2 에서  왼쪽 자식 3으로 갈때 [0, 1, 1, 0] 3에서 왼쪽 자식 4로 갈때 [0, 1, 1, 1]  요기서 if 문에 걸려서 배열 안의 값이 1인 인덱스 번호를 출력 하고 다시 3에서 오른쪽 자식 4로 이동합니다 [0, 1, 1, 0, ...] if 문에 걸려 다시 출력 이걸 반복합니다.