算法题（使用递归生成所有可能的子序列）

本文概述

C ++
Python3

给定一个数组。任务是使用递归生成并打印给定数组的所有可能的子序列。
例子：

Input : [1, 2, 3] Output : [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]Input : [1, 2] Output : [2], [1], [1, 2]

方法：
对于数组中的每个元素, 都有两种选择, 要么将其包含在子序列中, 要么不包含它。从索引0开始将其应用于数组中的每个元素, 直到到达最后一个索引。到达最后一个索引后, 打印子序列。
下图显示了数组的递归树,arr [] = {1, 2}.

文章图片
下面是上述方法的实现。
C ++

//C++ code to print all possible //subsequences for given array using //recursion #include < bits/stdc++.h> using namespace std; void printArray(vector< int> arr, int n) { for ( int i = 0; i < n; i++) cout < < arr[i] < < " " ; cout < < endl; }//Recursive function to print all //possible subsequences for given array void printSubsequences(vector< int> arr, int index, vector< int> subarr) { //Print the subsequence when reach //the leaf of recursion tree if (index == arr.size()) { int l = subarr.size(); //Condition to avoid printing //empty subsequence if (l != 0) printArray(subarr, l); } else { //Subsequence without including //the element at current index printSubsequences(arr, index + 1, subarr); subarr.push_back(arr[index]); //Subsequence including the element //at current index printSubsequences(arr, index + 1, subarr); } return ; }//Driver Code int main() { vector< int> arr{1, 2, 3}; vector< int> b; printSubsequences(arr, 0, b); return 0; }//This code is contributed by //sanjeev2552

Python3

# Python3 code to print all possible # subsequences for given array using # recursion # Recursive function to print all # possible subsequences for given array def printSubsequences(arr, index, subarr): # Print the subsequence when reach # the leaf of recursion tree if index = = len (arr): # Condition to avoid printing # empty subsequence if len (subarr) ! = 0 : print (subarr) else : # Subsequence without including # the element at current index printSubsequences(arr, index + 1 , subarr) # Subsequence including the element # at current index printSubsequences(arr, index + 1 , subarr + [arr[index]]) returnarr = [ 1 , 2 , 3 ] printSubsequences(arr, 0 , []) #This code is contributed by Mayank Tyagi

输出如下：