#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
#include<assert.h>

void Combination(char *string ,int number,vector<char> &result);

void Combination(char *string)
{
 assert(string != NULL);
 vector<char> result;
 int i , length = strlen(string);
 for(i = 1 ; i <= length ; ++i)
 Combination(string , i ,result);
}

void Combination(char *string ,int number , vector<char> &result)
{
 assert(string != NULL);
 if(number == 0)
 {
 static int num = 1;
 printf("第%d个组合\t",num++);

 vector<char>::iterator iter = result.begin();
 for( ; iter != result.end() ; ++iter)
  printf("%c",*iter);
 printf("\n");
 return ;
 }
 if(*string == '\0')
 return ;
 result.push_back(*string);
 Combination(string + 1 , number - 1 , result);
 result.pop_back();
 Combination(string + 1 , number , result);
}

int main(void)
{
 char str[] = "abc";
 Combination(str);
 return 0;
}

#include<iostream>
using namespace std;

int a[] = {1,3,5,4,6};
char str[] = "abcde";

void print_subset(int n , int s)
{
 printf("{");
 for(int i = 0 ; i < n ; ++i)
 {
 if( s&(1<<i) )     // 判断s的二进制中哪些位为1，即代表取某一位
  printf("%c ",str[i]);  //或者a[i]
 }
 printf("}\n");
}

void subset(int n)
{
 for(int i= 0 ; i < (1<<n) ; ++i)
 {
 print_subset(n,i);
 }
}



int main(void)
{
 subset(5);
 return 0;
}

  /** 
   * Write a method that returns all subsets of a set 
   */ 
   
  #include <stdio.h> 
  #include <stdlib.h> 
  #include <string.h> 
   
  /** 
   * 通过0到2^-1来标识子集 
   * 
   * T = (n * 2^n) 
   * 
   */ 
  void getSubset(char *str, int len) 
  { 
    int i, max, index, j; 
   
    max = 1 << len; 
   
    for (i = 1; i < max; i ++) { 
      j = i; 
      index = 0; 
   
      while (j) { 
        if (j & 1) { 
          printf("%c", str[index]); 
        } 
        j >>= 1; 
        index ++; 
      } 
      printf("\n"); 
    } 
  } 
   
  int main(void) 
  { 
    char str[1000]; 
   
    while (scanf("%s", str) != EOF) { 
      getSubset(str, strlen(str)); 
   
    } 
   
    return 0; 
  } 

  /** 
   * 递归法解决组合问题 
   */ 
  void combine(int *arr, int n, int m, int *tmp, const int M) 
  { 
    int i, j; 
   
    for (i = n; i >= m; i --) { 
      tmp[m] = i; 
      if (m == 0) {  // 选出m个数 
        for (j = 0; j < M; j ++) { 
          printf("%d ", arr[tmp[j]]); 
        } 
        printf("\n"); 
      } else { 
        combine(arr, i - 1, m - 1, tmp, M); 
      } 
    } 
  } 

  public class Solution { 
    public static ArrayList<ArrayList<Integer>> combine(int n, int k) { 
      ArrayList<ArrayList<Integer>> rs = new ArrayList<ArrayList<Integer>>(); 
      ArrayList<Integer> list = new ArrayList<Integer>(); 
       
      dfs(1, k, n, list, rs); 
       
      return rs; 
    } 
     
    public static void dfs(int pos, int k, int n, ArrayList<Integer> list, ArrayList<ArrayList<Integer>> rs) { 
      if (list.size() == k) { 
        rs.add(new ArrayList<Integer>(list)); 
      } 
       
      for (int i = pos; i <= n; i ++) { 
        list.add(i); 
        dfs(i + 1, k, n, list, rs); 
        list.remove(list.size() - 1); 
      } 
    } 
  }