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

本文概述

• 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]]) 
        
     return
            
arr = [ 1 , 2 , 3 ] 
    
printSubsequences(arr, 0 , []) 
  
#This code is contributed by Mayank Tyagi

输出如下：

[3]
[2]
[2, 3]
[1]
[1, 3]
[1, 2]
[1, 2, 3]

时间复杂度：

首先, 你的面试准备可通过以下方式增强你的数据结构概念：Python DS课程。

---