[문제풀이] 07-06. 부분 집합 구하기

인프런, 자바(Java) 알고리즘 문제풀이

Recursive, Tree, Graph - 0706. 부분 집합 구하기(DFS)

🗒️ 문제

🎈 나의 풀이

	private static int[] ch;
    
    private static void DFS(int n) {
        if(n == ch.length) {
            String str = "";

            for(int i=0; i<ch.length; i++) {
                if(ch[i] == 1) str+=i;
            }

            if(!str.equals("")) System.out.println(str);

        } else {
            ch[n] = 1;
            DFS(n+1);
            ch[n] = 0;
            DFS(n+1);
        }

    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ch = new int[n + 1];
        DFS(1);
    }

🖍️ 강의 풀이

  	static int n;
	static int[] ch;
	public void DFS(int L){
		if(L==n+1){
			String tmp="";
			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);
	}	

💬 짚어가기

해당 문제는 부분 집합을 출력하는 문제이다. DFS를 이용해 풀이하였다. n개의 요소로 이루어진
부분 집합의 경우의 수는 n을 포함하는 경우와 그렇지 않은 경우로 $2^n$의 경우의 수가 나온다.

따라서 코드에서는 해당 요소의 사용 여부를 기록할 수있는 배열을 하나 생성하고, DFS 탐색을
수행하기전, 해당 요소의 index에 1 또는 0을 보관하여 사용 여부를 구분한다.