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

2021年4月9日16:58:42 发表评论 1,018 次浏览

## 本文概述

``````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]``````

## 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]``````