剑指offer-拓展训练-字符的所有组合-全组合

/*

题目：

	给定不含重复字符字符串的全组合。

*/

/*

思路：

	递归法。

	例给定abc，输出的组合长度为1，2，3.

	对于长度为2的组合，分选择a(ab,ac)和不选择a的情况(bc)。

	选择a，则在剩余字符串中选择长度为1的字符组合；

	不选择a，则在剩余字符串中选择长度为2的字符组合。

*/

#include<iostream>

#include<stdio.h>

#include<string>

using namespace std;

string curr;

void combination(string str,int len,int beginIndex){

	//当遍历到字符串的末尾，但所需长度不够，直接返回。

    if(beginIndex == str.size()  && len != 0){

        return;

    }

	//当长度足够，则输出当前字符串。

    if(len == 0 ){

        cout<<curr<<" ";

    }else{

		//选择当前字符串的情况

        curr+=(str[beginIndex]);

        combination(str,len-1,beginIndex+1);

		//不选择当前字符串的情况

        curr.erase(curr.size()-1);

        combination(str,len,beginIndex+1);

    }

}

int main(){

    string str;

    while(getline(cin,str)){

        if(str == "")

            cout<<endl;

        else{

            for(int len = 1; len <= str.size(); len++){

                combination(str,len,0);

                cout<<endl;

            }

        }

    }

}