[기초 알고리즘] 수학: 멱집합

1. 멱집합 (Power Set)

• 임의의 집합 S에서 모든 부분 집합들로 구성된 집합입니다.
• ${\displaystyle {\mathcal {P}}(S)=\{A\colon A\subseteq S\}}$

 

코드

private void powerset(int depth) {
    if (depth == size) {
        List<String> temp = new ArrayList<>();
        for (int i = 0; i < visited.length; i++) {
            if (!visited[i]) continue;
                
            temp.add(String.valueOf(src[i]));
        }
        
        System.out.println(Arrays.toString(temp));
        return;
    }

    visited[depth] = false;
    powerset(depth+1);
    visited[depth] = true;
    powerset(depth+1);
}

 

예

${\displaystyle \{a,b\}}$의 멱집합

• ${\displaystyle {\mathcal {P}}(\{a,b\})=\{\varnothing ,\{a\},\{b\},\{a,b\}\}}$

 

${\displaystyle \{a,b,c\}}$의 멱집합

• ${\displaystyle {\mathcal {P}}(\{a,b,c\})=\{\varnothing ,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}}$

 

출처

• Wiki - Power Set