Выведите суммы всех подмножеств данного набора
Для массива целых чисел выведите суммы всех подмножеств в нем. Суммы вывода можно распечатать в любом порядке.
Примеры :
Ввод: arr [] = {2, 3}
Выход: 0 2 3 5
Ввод: arr [] = {2, 4, 5}
Выход: 0 2 4 5 6 7 9 11Method 1 (Recursive)
We can recursively solve this problem. There are total 2n subsets. For every element, we consider two choices, we include it in a subset and we don’t include it in a subset. Below is recursive solution based on this idea.
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 codeint 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 codearr = [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.?> |
Javascript
<script>// Javascript program to program to print// sums of all possible subsets.// Prints sums of all// subsets of arr[l..r]function subsetSums(arr, l, r, sum){ // Print current subset if (l > r) { document.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 codelet arr = [5, 4, 3];let n = arr.length;subsetSums(arr, 0, n - 1, 0);// This code is contributed by code_hunt </script> |
Выход :
12 9 8 5 7 4 3 0
Временная сложность этого решения составляет O (2 ^ n), а пространственная сложность - O (n).
Method 2 (Iterative)
As discussed above, there are total 2n subsets. The idea is generate loop from 0 to 2n – 1. For every number, pick all array elements which correspond to 1s in binary representation of current number.
C++
// Iterative C++ program to print sums of all// possible subsets.#include <bits/stdc++.h>using namespace std;// Prints sums of all subsets of arrayvoid 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 codeint 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 arrayfunction 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?> |
Javascript
<script> // Iterative Javascript 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 let total = 1 << n; // Consider all numbers from 0 to 2^n - 1 for(let i = 0; i < total; i++) { let sum = 0; // Consider binary reprsentation of // current i to decide which elements // to pick. for(let j = 0; j < n; j++) if ((i & (1 << j)) != 0) sum += arr[j]; // Print sum of picked elements. document.write(sum + " "); } } let arr = [ 5, 4, 3 ]; let n = arr.length; subsetSums(arr, n); </script> |
Выход :
0 5 4 9 3 8 7 12
Спасибо cfh за предложение вышеупомянутого итеративного решения в комментарии.
Примечание. На самом деле мы не создавали подмножества для нахождения их сумм, а просто использовали рекурсию для нахождения суммы несмежных подмножеств данного набора.
Вышеупомянутые методы могут использоваться для выполнения различных операций с подмножествами, таких как умножение, деление, XOR, OR и т. Д., Без фактического создания и сохранения подмножеств и, таким образом, повышения эффективности памяти программы.
Эта статья предоставлена Адитьей Гуптой. Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью, используя write.geeksforgeeks.org, или отправить свою статью по электронной почте: deposit@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсуждаемой выше. Неверно, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.