[알고리즘] 부분집합(DFS)

ho's·2022년 7월 6일
0

🍜부분집합

🥡 문제

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

🥡 풀이

🥡 소스코드

package dfs_bfs;
public class Main {
    static int n;
    static int[] ch;
    public void DFS(int L){
        if(L==n+1){
            String tmp = "";
            // n을 static으로 한 이유.
            // static메소드가 접근해야 하기 때문에.
            for(int i=1;i<=n;i++){
                if(ch[i] == 1)
                    tmp += (i+" ");
            }
            if(tmp.length() >0)
                System.out.println(tmp);
        }
        else{
            ch[L] = 1;
            DFS(L+1);
            ch[L] = 0;
            DFS(L+1);
        }
    }

    public static void main(String[] args) {
        Main T = new Main();
        n = 3;
        ch = new int[n+1];
        T.DFS(1);
    }
}
profile
그래야만 한다

0개의 댓글