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

本文概述

C ++
Java
Python3
C#
的PHP

给定一个数组和一个数字, 请打印总和等于给定总和的所有子集。
【如何使用递归实现打印给定总和的所有子集（）】例子：

Input :arr[] ={2, 5, 8, 4, 6, 11}, sum = 13 Output : 5 8 2 11 2 5 6Input : 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 codearr = [ 2 , 5 , 8 , 4 , 6 , 11 ] sum = 13 n = len (arr) printAllSubsets(arr, n, sum )# This code is contributed by ihritik

// 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 ?>

输出如下：