算法题（打印一组给定大小的所有子集） _数据结构

本文概述

C ++
Java
Python3
C#
的PHP

生成给定数组中具有不同元素的所有大小为r的可能子集。
例子：

Input: arr[] = {1, 2, 3, 4} r = 2 Output :1 2 1 3 1 4 2 3 2 4 3 4Input: arr[] = {10, 20, 30, 40, 50} r = 3 Output : 10 20 30 10 20 40 10 20 50 10 30 40 10 30 50 10 40 50 20 30 40 20 30 50 20 40 50 30 40 50

这个问题和在大小为n的给定数组中打印r元素的所有可能组合.
这里的想法类似于子集总和问题。我们一个接一个地考虑输入数组的每个元素, 然后重复两种情况：
1)元素包含在当前组合中(我们将元素放入data []中, 并在data []中增加下一个可用索引)
2)当前组合中不包含该元素(我们不放置该元素并且不更改索引)
当data []中的元素数等于r(组合的大小)时, 我们将其打印出来。
该方法主要基于帕斯卡的身份, 即?C[R= n-1C[R+ n-1C1一
C ++

//Program to print all combination of size r in //an array of size n #include < stdio.h> void combinationUtil( int arr[], int n, int r, int index, int data[], int i); //The main function that prints all combinations of //size r in arr[] of size n. This function mainly //uses combinationUtil() void printCombination( int arr[], int n, int r) { //A temporary array to store all combination //one by one int data[r]; //Print all combination using temprary array 'data[]' combinationUtil(arr, n, r, 0, data, 0); }/* arr[]---> Input Array n---> Size of input array r---> Size of a combination to be printed index---> Current index in data[] data[] ---> Temporary array to store current combination i---> index of current element in arr[]*/ void combinationUtil( int arr[], int n, int r, int index, int data[], int i) { //Current cobination is ready, print it if (index == r) { for ( int j = 0; j < r; j++) printf ( "%d " , data[j]); printf ( "\n" ); return ; }//When no more elements are there to put in data[] if (i> = n) return ; //current is included, put next at next location data[index] = arr[i]; combinationUtil(arr, n, r, index + 1, data, i + 1); //current is excluded, replace it with next //(Note that i+1 is passed, but index is not //changed) combinationUtil(arr, n, r, index, data, i + 1); }//Driver program to test above functions int main() { int arr[] = { 10, 20, 30, 40, 50 }; int r = 3; int n = sizeof (arr) /sizeof (arr[0]); printCombination(arr, n, r); return 0; }

Java

//Java program to print all combination of size //r in an array of size n import java.io.*; class Permutation {/* arr[]---> Input Array data[] ---> Temporary array to store current combination start & end ---> Staring and Ending indexes in arr[] index---> Current index in data[] r ---> Size of a combination to be printed */ static void combinationUtil( int arr[], int n, int r, int index, int data[], int i) { //Current combination is ready to be printed, //print it if (index == r) { for ( int j = 0 ; j < r; j++) System.out.print(data[j] + " " ); System.out.println( "" ); return ; }//When no more elements are there to put in data[] if (i> = n) return ; //current is included, put next at next //location data[index] = arr[i]; combinationUtil(arr, n, r, index + 1 , data, i + 1 ); //current is excluded, replace it with //next (Note that i+1 is passed, but //index is not changed) combinationUtil(arr, n, r, index, data, i + 1 ); }//The main function that prints all combinations //of size r in arr[] of size n. This function //mainly uses combinationUtil() static void printCombination( int arr[], int n, int r) { //A temporary array to store all combination //one by one int data[] = new int [r]; //Print all combination using temprary //array 'data[]' combinationUtil(arr, n, r, 0 , data, 0 ); }/* Driver function to check for above function */ public static void main(String[] args) { int arr[] = { 10 , 20 , 30 , 40 , 50 }; int r = 3 ; int n = arr.length; printCombination(arr, n, r); } } /* This code is contributed by Devesh Agrawal */

Python3

# Python program to print all # subset combination of n # element in given set of r element .# arr[] ---> Input Array # data[] ---> Temporary array to #store current combination # start & end ---> Staring and Ending #indexes in arr[] # index ---> Current index in data[] # r ---> Size of a combination #to be printed def combinationUtil(arr, n, r, index, data, i): # Current combination is # ready to be printed, # print it if (index = = r): for j in range (r): print (data[j], end = " " ) print ( " " ) return# When no more elements # are there to put in data[] if (i> = n): return# current is included, # put next at next # location data[index] = arr[i] combinationUtil(arr, n, r, index + 1 , data, i + 1 )# current is excluded, # replace it with # next (Note that i+1 # is passed, but index # is not changed) combinationUtil(arr, n, r, index, data, i + 1 )# The main function that # prints all combinations # of size r in arr[] of # size n. This function # mainly uses combinationUtil() def printcombination(arr, n, r):# A temporary array to # store all combination # one by one data = https://www.lsbin.com/list ( range (r))# Print all combination # using temporary # array'data[]' combinationUtil(arr, n, r, 0 , data, 0 )# Driver Code arr = [ 10 , 20 , 30 , 40 , 50 ]r = 3 n = len (arr) printcombination(arr, n, r)# This code is contributed # by Ambuj sahu

//C# program to print all combination //of size r in an array of size n using System; class GFG {/* arr[] ---> Input Array data[] ---> Temporary array to store current combination start & end ---> Staring and Ending indexes in arr[] index ---> Current index in data[] r ---> Size of a combination to be printed */ static void combinationUtil( int []arr, int n, int r, int index, int []data, int i) {//Current combination is ready to //be printed, print it if (index == r) { for ( int j = 0; j < r; j++) Console.Write(data[j] + " " ); Console.WriteLine( "" ); return ; }//When no more elements are there //to put in data[] if (i> = n) return ; //current is included, put next //at next location data[index] = arr[i]; combinationUtil(arr, n, r, index + 1, data, i + 1); //current is excluded, replace //it with next (Note that i+1 //is passed, but index is not //changed) combinationUtil(arr, n, r, index, data, i + 1); }//The main function that prints all //combinations of size r in arr[] of //size n. This function mainly uses //combinationUtil() static void printCombination( int []arr, int n, int r) {//A temporary array to store all //combination one by one int []data = https://www.lsbin.com/new int [r]; //Print all combination using //temprary array'data[]' combinationUtil(arr, n, r, 0, data, 0); }/* Driver function to check for above function */ public static void Main() { int []arr = { 10, 20, 30, 40, 50 }; int r = 3; int n = arr.Length; printCombination(arr, n, r); } }//This code is contributed by vt_m.

的PHP

< ?php //Program to print all combination of //size r in an array of size n//The main function that prints all //combinations of size r in arr[] of //size n. This function mainly uses //combinationUtil() function printCombination( $arr , $n , $r ) { //A temporary array to store all //combination one by one $data = https://www.lsbin.com/array (); //Print all combination using //temprary array'data[]' combinationUtil( $arr , $n , $r , 0, $data , 0); }/* arr[] ---> Input Array n ---> Size of input array r ---> Size of a combination to be printed index ---> Current index in data[] data[] ---> Temporary array to store current combination i ---> index of current element in arr[] */ function combinationUtil( $arr , $n , $r , $index , $data , $i ) { //Current cobination is ready, print it if ( $index == $r ) { for ( $j = 0; $j < $r ; $j ++) echo $data [ $j ], " " ; echo "\n" ; return ; }//When no more elements are there to //put in data[] if ( $i> = $n ) return ; //current is included, put next at //next location $data [ $index ] = $arr [ $i ]; combinationUtil( $arr , $n , $r , $index + 1, $data , $i + 1); //current is excluded, replace it with //next (Note that i+1 is passed, but //index is not changed) combinationUtil( $arr , $n , $r , $index , $data , $i + 1); }//Driver program to test above functions $arr = array ( 10, 20, 30, 40, 50 ); $r = 3; $n = count ( $arr ); printCombination( $arr , $n , $r ); //This code is contributed by anuj_67. ?>

输出如下：