Counting Subsets

https://rosalind.info/problems/sset/

ROSALIND | Counting Subsets

Problem

A set is the mathematical term for a loose collection of objects, called elements. Examples of sets include {the moon, the sun, Wilford Brimley}{the moon, thesun, Wilford Brimley} and RR, the set containing all real numbers. We even have the empty set, represented by ∅∅ or {}{}, which contains no elements at all. Two sets are equal when they contain the same elements. In other words, in contrast to permutations, the ordering of the elements of a set is unimportant (e.g., {the moon, the sun, Wilford Brimley}{the moon, the sun, Wilford Brimley} is equivalent to {Wilford Brimley, the moon, the sun}{Wilford Brimley, the moon, the sun}). Sets are not allowed to contain duplicate elements, so that {Wilford Brimley, the sun, the sun}{Wilford Brimley, the sun, the sun} is not a set. We have already used sets of 2 elements to represent edges from a graph.

A set AA is a subset of BB if every element of AA is also an element of BB, and we write A⊆BA⊆B. For example, {the sun, the moon}⊆{the sun, the moon, Wilford Brimley}{the sun, the moon}⊆{the sun,the moon, Wilford Brimley}, and ∅∅ is a subset of every set (including itself!).

As illustrated in the biological introduction, we can use subsets to represent the collection of taxa possessing a character. However, the number of applications is endless; for example, an event in probability can now be defined as a subset of the set containing all possible outcomes.

Our first question is to count the total number of possible subsets of a given set.

Given: A positive integer nn (n≤1000n≤1000).

Return: The total number of subsets of {1,2,…,n}{1,2,…,n} modulo 1,000,000.

Sample Dataset

3

Sample Output

8

 

 이 문제는 1~n 까지 있는 집합의 부분집합의 총 개수를 구하는 문제이다. 부분집합은 원래 집합에서 몇 개를 순서없이 고르는 것과 같으므로 조합을 이용해서 고를 수 있다. 0~n개를 고르는 조합의 개수를 다 구해주면 된다.

def factorial(n):
    v=1
    for i in range(1,n+1):
        v*=i
    return v

N=int(input())
ans=0
for i in range(N+1):
    ans+=(factorial(N)//(factorial(i)*factorial(N-i)))

print(ans%1000000)