本文概述
- 建议：在继续解决方案之前, 请先在"实践"上解决它。
- C ++
- Java
- Python3
- C#
- 的PHP
- C ++
- Java
- 的PHP
例子 ：
Input : arr[] = {2, 3}
Output: 0 2 3 5Input : arr[] = {2, 4, 5}
Output : 0 2 4 5 6 7 9 11推荐：请在"实践首先, 在继续解决方案之前。方法1(递归)
我们可以递归地解决这个问题。总共有2^n个子集。对于每个元素，我们有两种选择，将其包含在一个子集中，也不将其包含在一个子集中。下面是基于此思想的递归解。
C ++
// C++ program to print sums of all possible
// subsets.
#include<
bits/stdc++.h>
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_67Python3
# 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的PHP
<
?php
// PHP program to print sums
// of all possible subsets.// Prints sums of all
// subsets of arr[l..r]
function subsetSums( $arr , $l , $r , $sum = 0)
{
// Print current subset
if ( $l >
$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.
?>
输出：
12 9 8 5 7 4 3 0方法2(迭代)
如上所述，总共有2^n个子集。这个想法是从0到2^n - 1生成循环。对于每一个数字，选择在当前数字的二进制表示中对应于1的所有数组元素。
C ++
// Iterative C++ program to print sums of all
// possible subsets.
#include<
bits/stdc++.h>
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 reprsentation 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 reprsentation 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____的PHP
<
?php
// Iterative PHP program to print
// sums of all possible subsets. // Prints sums of all subsets of array
function subsetSums( $arr , $n )
{ // There are totoal 2^n subsets
$total = 1 <
<
$n ;
// Consider all numbers
// from 0 to 2^n - 1
for ( $i = 0;
$i <
$total ;
$i ++)
{
$sum = 0;
// Consider binary reprsentation of
// current i to decide which elements
// to pick.
for ( $j = 0;
$j <
$n ;
$j ++)
if ( $i &
(1 <
<
$j ))
$sum += $arr [ $j ];
// Print sum of picked elements.
echo $sum , " " ;
}
} // Driver code
$arr = array (5, 4, 3);
$n = sizeof( $arr );
subsetSums( $arr , $n );
// This Code is Contributed by ajit
?>
输出：
0 5 4 9 3 8 7 12感谢cfh在评论中建议上述迭代解决方案。
注意：我们实际上并未创建子集来查找它们的总和, 而是仅使用了递归来找到给定集合的非连续子集的总和。
上述技术可用于对子集执行各种运算, 例如乘法, 除法, XOR, OR等, 而无需实际创建和存储子集, 从而使程序存储器高效。
【算法设计（打印给定集合的所有子集的总和）】如果发现任何不正确的内容, 或者你??想共享有关上述主题的更多信息, 请写评论。正确的, 或者你想要共享有关以上讨论的主题的更多信息
推荐阅读
- jQuery中如何检查字符串以特定字符串开头/结尾（）
- 算法（检查二叉树是否包含大小为2或更大的重复子树）
- Python如何从列表中删除空元组（）
- IP寻址和无类寻址简介
- PHP Ds Map apply()函数用法示例
- Python Tkinter如何使用标签小工具（示例）
- CSS如何使用Web字体（详细代码示例）
- JavaScript如何使用Date now()方法（）
- PHP如何使用parse_url()函数（代码示例）