左神算法基础class8—题目3打印字符串的全部子序列

1.题目:打印一个字符串的全部子序列，包括空字符串

2.分析

假如字符串为abc，所有子串的可能为：空,a,ab,ac,abc,b,bc,c

对于字符串的每一个元素，我们都可以选择要或者不要，如下图，如果需要当前元素，获得一个“a”第一个元素不需要的话那么第一个就是“ ”，再接着向后判断，b元素依然可以选择需要或者不需要，那么就有四种可能“ab”，“a ”，“ b”，“ ”。对下一个元素c也是同理。整个递归的结束条件是当前索引不在字符串内

3.完整代码

#include<iostream>
#include<string>
using namespace std;

//s是给定的字符串，i是索引，res是结果
void print(const string s,int i,string res)
{
	if(i == s.size())	//超出索引，打印上一级传递的结果
	{
		cout<<res<<endl;
		return;
	}
	else
	{
		print(s,i + 1,res + s[i]);	//添加当前字符
		print(s,i + 1,res );		//丢弃当前字符
	}
}

int main()
{
	string s = "abc";
	string res;
	print(s,0,res );

	return 0;
}