本文概述
- 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
输出如下:
[3]
[2]
[2, 3]
[1]
[1, 3]
[1, 2]
[1, 2, 3]
时间复杂度:
文章图片
【算法题(使用递归生成所有可能的子序列)】首先, 你的面试准备可通过以下方式增强你的数据结构概念:Python DS课程。
推荐阅读
- Scala Varargs可变参数用法详细介绍和示例
- Bash程序检查Number是否为质数
- Python OpenCV仿射变换实现详细指南
- SASS如何使用占位符选择器(用法示例)
- Python使用Pandas处理日期和时间
- 如何在JavaScript中创建二维数组()
- 进展问题(AP,GP,HP)详细介绍
- CSS边框属性用法示例
- 亚马逊面试题分享|S54(实习)