算法设计：打印给定集合的所有子集的总和

2021年3月20日15:55:48 发表评论 695 次浏览

本文概述

给定一个整数数组, 输出其中所有子集的和。输出总和可以按任何顺序打印。

例子 ：

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个子集。对于每个元素，我们有两种选择，将其包含在一个子集中，也不将其包含在一个子集中。下面是基于此思想的递归解。

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_67

Python3

# 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等, 而无需实际创建和存储子集, 从而使程序存储器高效。

如果发现任何不正确的内容, 或者你​​想共享有关上述主题的更多信息, 请写评论。正确的, 或者你想要共享有关以上讨论的主题的更多信息

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: