如何使用递归实现打印给定总和的所有子集？

本文概述

• C ++
• Java
• Python3
• C#
• 的PHP

给定一个数组和一个数字, 请打印总和等于给定总和的所有子集。

例子：

Input :  arr[] =  {2, 5, 8, 4, 6, 11}, sum = 13
Output : 
5 8
2 11
2 5 6

Input : arr[] =  {1, 5, 8, 4, 6, 11}, sum = 9
Output :
5 4
1 8

这个问题是:检查是否有给定总和的子集。我们递归生成所有子集。我们跟踪当前子集的元素。如果当前子集中的元素总和等于给定总和, 我们将打印该子集。

C ++

// CPP program to print all subsets with given sum
#include <bits/stdc++.h>
using namespace std;
  
// The vector v stores current subset.
void printAllSubsetsRec( int arr[], int n, vector< int > v, int sum)
{
     // If remaining sum is 0, then print all
     // elements of current subset.
     if (sum == 0) {
         for ( auto x : v)
             cout << x << " " ;
         cout << endl;
         return ;
     }
  
     // If no remaining elements, if (n == 0)
         return ;
  
     // We consider two cases for every element.
     // a) We do not include last element.
     // b) We include last element in current subset.
     printAllSubsetsRec(arr, n - 1, v, sum);
     v.push_back(arr[n - 1]);
     printAllSubsetsRec(arr, n - 1, v, sum - arr[n - 1]);
}
  
// Wrapper over printAllSubsetsRec()
void printAllSubsets( int arr[], int n, int sum)
{
     vector< int > v;
     printAllSubsetsRec(arr, n, v, sum);
}
  
// Driver code
int main()
{
     int arr[] = { 2, 5, 8, 4, 6, 11 };
     int sum = 13;
     int n = sizeof (arr) / sizeof (arr[0]);
     printAllSubsets(arr, n, sum);
     return 0;
}

Java

// Java program to print all subsets with given sum 
import java.util.*;
  class Solution
{
  
// The vector v stores current subset. 
static void printAllSubsetsRec( int arr[], int n, Vector<Integer> v, int sum) 
{ 
     // If remaining sum is 0, then print all 
     // elements of current subset. 
     if (sum == 0 ) { 
         for ( int i= 0 ;i<v.size();i++) 
             System.out.print( v.get(i) + " " ); 
         System.out.println();
         return ; 
     } 
  
     // If no remaining elements, if (n == 0 ) 
         return ; 
  
     // We consider two cases for every element. 
     // a) We do not include last element. 
     // b) We include last element in current subset. 
     printAllSubsetsRec(arr, n - 1 , v, sum); 
     Vector<Integer> v1= new Vector<Integer>(v);
     v1.add(arr[n - 1 ]); 
     printAllSubsetsRec(arr, n - 1 , v1, sum - arr[n - 1 ]); 
} 
  
// Wrapper over printAllSubsetsRec() 
static void printAllSubsets( int arr[], int n, int sum) 
{ 
     Vector<Integer> v= new Vector<Integer>(); 
     printAllSubsetsRec(arr, n, v, sum); 
} 
  
// Driver code 
public static void main(String args[]) 
{ 
     int arr[] = { 2 , 5 , 8 , 4 , 6 , 11 }; 
     int sum = 13 ; 
     int n = arr.length; 
     printAllSubsets(arr, n, sum); 
      
}
} 
//contributed by Arnab Kundu

Python3

# Python program to print all subsets with given sum
  
# The vector v stores current subset.
def printAllSubsetsRec(arr, n, v, sum ) :
  
     # If remaining sum is 0, then print all
     # elements of current subset.
     if ( sum = = 0 ) :
         for value in v :
             print (value, end = " " )
         print ()
         return
      
  
     # If no remaining elements, if (n = = 0 ):
         return
  
     # We consider two cases for every element.
     # a) We do not include last element.
     # b) We include last element in current subset.
     printAllSubsetsRec(arr, n - 1 , v, sum )
     v1 = [] + v
     v1.append(arr[n - 1 ])
     printAllSubsetsRec(arr, n - 1 , v1, sum - arr[n - 1 ])
  
  
# Wrapper over printAllSubsetsRec()
def printAllSubsets(arr, n, sum ):
  
     v = []
     printAllSubsetsRec(arr, n, v, sum )
  
  
# Driver code
  
arr = [ 2 , 5 , 8 , 4 , 6 , 11 ]
sum = 13
n = len (arr)
printAllSubsets(arr, n, sum )
  
# This code is contributed by ihritik

C#

// C# program to print all subsets with given sum 
using System;
using System.Collections.Generic;
  
class GFG 
{ 
     // The vector v stores current subset. 
     static void printAllSubsetsRec( int []arr, int n, List< int > v, int sum) 
     { 
         // If remaining sum is 0, then print all 
         // elements of current subset. 
         if (sum == 0)
         { 
             for ( int i = 0; i < v.Count; i++) 
                 Console.Write( v[i]+ " " ); 
             Console.WriteLine(); 
             return ; 
         } 
  
         // If no remaining elements, if (n == 0) 
             return ; 
  
         // We consider two cases for every element. 
         // a) We do not include last element. 
         // b) We include last element in current subset. 
         printAllSubsetsRec(arr, n - 1, v, sum); 
         List< int > v1 = new List< int >(v); 
         v1.Add(arr[n - 1]); 
         printAllSubsetsRec(arr, n - 1, v1, sum - arr[n - 1]); 
     } 
  
     // Wrapper over printAllSubsetsRec() 
     static void printAllSubsets( int []arr, int n, int sum) 
     { 
         List< int > v = new List< int >(); 
         printAllSubsetsRec(arr, n, v, sum); 
     } 
  
     // Driver code 
     public static void Main() 
     { 
         int []arr = { 2, 5, 8, 4, 6, 11 }; 
         int sum = 13; 
         int n = arr.Length; 
         printAllSubsets(arr, n, sum); 
     } 
} 
  
// This code is contributed by Rajput-Ji

的PHP

<?php
// PHP program to print all subsets with given sum
  
// The vector v stores current subset.
function printAllSubsetsRec( $arr , $n , $v , $sum )
{
     // If remaining sum is 0, then print all
     // elements of current subset.
     if ( $sum == 0) 
     {
         for ( $i = 0; $i < count ( $v ); $i ++) 
             echo $v [ $i ] . " " ;
         echo "\n" ;
         return ;
     }
  
     // If no remaining elements, if ( $n == 0)
         return ;
  
     // We consider two cases for every element.
     // a) We do not include last element.
     // b) We include last element in current subset.
     printAllSubsetsRec( $arr , $n - 1, $v , $sum );
     array_push ( $v , $arr [ $n - 1]);
     printAllSubsetsRec( $arr , $n - 1, $v , $sum - $arr [ $n - 1]);
}
  
// Wrapper over printAllSubsetsRec()
function printAllSubsets( $arr , $n , $sum )
{
     $v = array ();
     printAllSubsetsRec( $arr , $n , $v , $sum );
}
  
// Driver code
$arr = array ( 2, 5, 8, 4, 6, 11 );
$sum = 13;
$n = count ( $arr );
printAllSubsets( $arr , $n , $sum );
  
// This code is contributed by mits
?>

输出如下：

8 5 
6 5 2 
11 2

时间复杂度：O(2^n)

请参考下面的帖子, 以获得基于动态编程的优化解决方案。

使用动态编程打印给定总和的所有子集

---