原文:
给定一个整数数组，打印其中所有子集的和。输出总和可以以任何顺序打印。
示例:
input : arr[] = {2, 3}
output: 0 2 3 5
input : arr[] = {2, 4, 5}
output : 0 2 4 5 6 7 9 11
方法 1(递归) 我们可以递归解决这个问题。总共有 2 个 n 个子集。对于每个元素，我们考虑两个选择，我们将它包含在一个子集中，而不将其包含在一个子集中。以下是基于这一思想的递归pg电子试玩链接的解决方案。
c
// c program to print sums of all possible
// subsets.
#include
using namespace std;
// prints sums of all subsets of arr[l..r]
void subsetsums(int arr[], int l, int r, int sum = 0)
{
// print current subset
if (l > r) {
cout << sum << " ";
return;
}
// subset including arr[l]
subsetsums(arr, l 1, r, sum arr[l]);
// subset excluding arr[l]
subsetsums(arr, l 1, r, sum);
}
// driver code
int main()
{
int arr[] = { 5, 4, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
subsetsums(arr, 0, n - 1);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program to print sums
// of all possible subsets.
import java.io.*;
class gfg {
// prints sums of all
// subsets of arr[l..r]
static void subsetsums(int[] arr, int l, int r, int sum)
{
// print current subset
if (l > r) {
system.out.print(sum " ");
return;
}
// subset including arr[l]
subsetsums(arr, l 1, r, sum arr[l]);
// subset excluding arr[l]
subsetsums(arr, l 1, r, sum);
}
// driver code
public static void main(string[] args)
{
int[] arr = { 5, 4, 3 };
int n = arr.length;
subsetsums(arr, 0, n - 1, 0);
}
}
// this code is contributed by anuj_67
python 3
# python3 program to print sums of
# all possible subsets.
# prints sums of all subsets of arr[l..r]
def subsetsums(arr, l, r, sum=0):
# print current subset
if l > r:
print(sum, end=" ")
return
# subset including arr[l]
subsetsums(arr, l 1, r, sum arr[l])
# subset excluding arr[l]
subsetsums(arr, l 1, r, sum)
# driver code
arr = [5, 4, 3]
n = len(arr)
subsetsums(arr, 0, n - 1)
# this code is contributed by shreyanshi arun.
c
// c# program to print sums of all possible
// subsets.
using system;
class gfg {
// prints sums of all subsets of
// arr[l..r]
static void subsetsums(int[] arr, int l, int r, int sum)
{
// print current subset
if (l > r) {
console.write(sum " ");
return;
}
// subset including arr[l]
subsetsums(arr, l 1, r, sum arr[l]);
// subset excluding arr[l]
subsetsums(arr, l 1, r, sum);
}
// driver code
public static void main()
{
int[] arr = { 5, 4, 3 };
int n = arr.length;
subsetsums(arr, 0, n - 1, 0);
}
}
// this code is contributed by anuj_67
服务器端编程语言（professional hypertext preprocessor 的缩写）
$r)
{
echo $sum , " ";
return;
}
// subset including arr[l]
subsetsums($arr, $l 1, $r,
$sum $arr[$l]);
// subset excluding arr[l]
subsetsums($arr, $l 1, $r, $sum);
}
// driver code
$arr = array(5, 4, 3);
$n = count($arr);
subsetsums($arr, 0, $n - 1);
// this code is contributed by anuj_67.
?>
java 描述语言
输出:
12 9 8 5 7 4 3 0
这个解的时间复杂度是 o(2^n)，空间复杂度是 o(2^n).
方法 2(迭代) 如上所述，总共有 2 个 n 个子集。想法是生成从 0 到 2n–1 的循环。对于每个数字，选择当前数字的二进制表示中对应于 1 的所有数组元素。
c
// iterative c program to print sums of all
// possible subsets.
#include
using namespace std;
// prints sums of all subsets of array
void subsetsums(int arr[], int n)
{
// there are totoal 2^n subsets
long long total = 1 << n;
// consider all numbers from 0 to 2^n - 1
for (long long i = 0; i < total; i ) {
long long sum = 0;
// consider binary representation of
// current i to decide which elements
// to pick.
for (int j = 0; j < n; j )
if (i & (1 << j))
sum = arr[j];
// print sum of picked elements.
cout << sum << " ";
}
}
// driver code
int main()
{
int arr[] = { 5, 4, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
subsetsums(arr, n);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// iterative java program to print sums of all
// possible subsets.
import java.util.*;
class gfg {
// prints sums of all subsets of array
static void subsetsums(int arr[], int n)
{
// there are totoal 2^n subsets
int total = 1 << n;
// consider all numbers from 0 to 2^n - 1
for (int i = 0; i < total; i ) {
int sum = 0;
// consider binary representation of
// current i to decide which elements
// to pick.
for (int j = 0; j < n; j )
if ((i & (1 << j)) != 0)
sum = arr[j];
// print sum of picked elements.
system.out.print(sum " ");
}
}
// driver code
public static void main(string args[])
{
int arr[] = new int[] { 5, 4, 3 };
int n = arr.length;
subsetsums(arr, n);
}
}
// this code is contributed by spp____
python 3
# iterative python3 program to print sums of all possible subsets
# prints sums of all subsets of array
def subsetsums(arr, n):
# there are totoal 2^n subsets
total = 1 << n
# consider all numbers from 0 to 2^n - 1
for i in range(total):
sum = 0
# consider binary representation of
# current i to decide which elements
# to pick.
for j in range(n):
if ((i & (1 << j)) != 0):
sum = arr[j]
# print sum of picked elements.
print(sum, "", end = "")
arr = [ 5, 4, 3 ]
n = len(arr)
subsetsums(arr, n);
# this code is contributed by mukesh07.
c
// iterative c# program to print sums of all
// possible subsets.
using system;
class gfg {
// prints sums of all subsets of array
static void subsetsums(int[] arr, int n)
{
// there are totoal 2^n subsets
int total = 1 << n;
// consider all numbers from 0 to 2^n - 1
for (int i = 0; i < total; i ) {
int sum = 0;
// consider binary representation of
// current i to decide which elements
// to pick.
for (int j = 0; j < n; j )
if ((i & (1 << j)) != 0)
sum = arr[j];
// print sum of picked elements.
console.write(sum " ");
}
}
static void main() {
int[] arr = { 5, 4, 3 };
int n = arr.length;
subsetsums(arr, n);
}
}
// this code is contributed by divyesh072019.
服务器端编程语言（professional hypertext preprocessor 的缩写）
java 描述语言
输出:
0 5 4 9 3 8 7 12
时间复杂度: o( ) 辅助空间: o(1) 感谢 cfh 在评论中提出上述迭代解。 注意:我们实际上并没有创建子集来寻找它们的和，而是使用递归来寻找给定集合的非连续子集的和。
上述技术可用于对子集执行各种操作，如乘法、除法、异或等，而无需实际创建和存储子集，从而使程序存储器高效。 本文由 供稿。如果你喜欢 geeksforgeeks 并想投稿，你也可以使用写一篇文章或者把你的文章邮寄到 review-team@geeksforgeeks.org。看到你的文章出现在极客博客pg电子试玩链接主页上，帮助其他极客。 如果发现有不正确的地方，或者你想分享更多关于上面讨论的话题的信息，请写评论。不正确，或者你想分享更多关于上面讨论的话题的信息
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
