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

2021年3月29日14:12:40 发表评论 388 次浏览

## 本文概述

``````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);
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);
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``````