算法题：打印一组给定大小的所有子集

本文概述

• 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 4

Input  : 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 = 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#

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

输出如下：

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元素的所有可能组合

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。