集合中不同子集的数量
原文:https://www.geeksforgeeks.org/number-distinct-subsets-set/
给定 n 个不同元素的数组，计算子集的总数。 示例:
Input : {1, 2, 3}
Output : 8
Explanation
the array contain total 3 element.its subset
are {}, {1}, {2}, {3}, {1, 2}, {2, 3}, {3, 1}, {1, 2, 3}.
so the output is 8..
我们知道大小为 n 的集合的子集数是 2 n 这个公式是如何工作的？ 对于每一个元素，我们都有两个选择，要么挑，要么不挑。所以我们总共有 2 * 2 ……(n 次)选择，即 2 n 另一种解释是: 大小为 0 的子集数量=nC0T18】大小为 1 的子集数量= n C 1 大小为 2 的子集数量=nC2【T20.. 子集总数=nC0+nC1+nC2+…。+nCn=2n* 详见二项式系数之和。
C++
// CPP program to count number of distinct
// subsets in an array of distinct numbers
#include <bits/stdc++.h>
using namespace std;
// Returns 2 ^ n
int subsetCount(int arr[], int n)
{
return 1 << n;
}
/* Driver program to test above function */
int main()
{
int A[] = { 1, 2, 3 };
int n = sizeof(A) / sizeof(A[0]);
cout << subsetCount(A, n);
return 0;
}
Java 语言(一种计算机语言，尤用于创建网站)
// Java program to count number of distinct
// subsets in an array of distinct numbers
class GFG {
// Returns 2 ^ n
static int subsetCount(int arr[], int n)
{
return 1 << n;
}
/* Driver program to test above function */
public static void main(String[] args)
{
int A[] = { 1, 2, 3 };
int n = A.length;
System.out.println(subsetCount(A, n));
}
}
// This code is contributed by Prerna Saini.
Python 3
# Python3 program to count number
# of distinct subsets in an
# array of distinct numbers
import math
# Returns 2 ^ n
def subsetCount(arr, n):
return 1 << n
# driver code
A = [ 1, 2, 3 ]
n = len(A)
print(subsetCount(A, n))
# This code is contributed by Gitanjali.
C
// C# program to count number of distinct
// subsets in an array of distinct numbers
using System;
class GFG {
// Returns 2 ^ n
static int subsetCount(int []arr, int n)
{
return 1 << n;
}
// Driver program
public static void Main()
{
int []A = { 1, 2, 3 };
int n = A.Length;
Console.WriteLine(subsetCount(A, n));
}
}
// This code is contributed by vt_m.
服务器端编程语言（Professional Hypertext Preprocessor 的缩写）
<?php
// PHP program to count
// number of distinct
// subsets in an array
// of distinct numbers
// Returns 2 ^ n
function subsetCount($arr, $n)
{
return 1 << $n;
}
// Driver Code
$A = array( 1, 2, 3 );
$n = sizeof($A);
echo(subsetCount($A, $n));
// This code is contributed by Ajit.
?>
java 描述语言
<script>
// JavaScript program to count number of distinct
// subsets in an array of distinct numbers
// Returns 2 ^ n
function subsetCount(arr, n)
{
return 1 << n;
}
// Driver code
let A = [ 1, 2, 3 ];
let n = A.length;
document.write(subsetCount(A, n));
</script>
Output:
8
版权属于：月萌API www.moonapi.com，转载请注明出处
