목표 부분집합의 원소를 구할 수 있다. 부분집합의 개수를 구할 수 있다. 이번 부분집합에서는 위 두가지 목표에 대해 조합을 통한 구현과 bitmask를 통한 구현을 알아보겠습니다. 구현 RecursiveSubset 첫번째는 조합을 이용한 풀이인데, 조합에 대한 코드나 지식이 부족하다면 여기를 참고하세요. 부분집합은 " 멱집합(개수) = nC0 + nC1 + nC2 + ... nCr + nCr+1 ... + nCn" 와 같은 성질을 가지고 있습니다. 조합 함수에 파라미터로 r을 넘겨주면 쉽게 구할 수 있습니다. void Comb(int idx, int curr, int r) { if (idx == r) { for (int i = 0; i < r; ++i) cout

개념 서로 다른 n개의 수 중에 r개를 선택 nCr = n! / (n-r)! * r! 리스트를 순서에 상관없이 수를 뽑는 것입니다. 사실 완전탐색으로 풀리는 문제가 있지만 많은 문제들이 그렇지 않습니다. 그럴때 최적화를 하여 답을 도출해 내는것이 중요한데, 최적화하기 앞서서 기본 뼈대가되는 탐색인 조합탐색을 알아보도록 하겠습니다. 구현 재귀 호출을 이용해서 조합을 구성하기 위해서는 네가지 파라미터가 필요합니다. nCr에서 n nCr에서 r 기저 조건을 위한 idx 어느곳을 탐색할지 정하는 curr 그러나 n과 r이 고정되어 있다면 idx와 curr만 사용할수도 있습니다. 이처럼 재귀 호출은 변형에 용이합니다. 그리고 아래와 같은 배열 2가지가 필요합니다. 나열한 수를 담을 배열 나열되어져야 할 수를 담은..