字符串组合算法 - c++编程基础

全组合

例如给定字符串“abc”，全组合意思从中去0个元素，1个元素，一直到n个元素，介绍二进制做法。以字符串“abc”为例：

000 <---> NULL

001 <---> c

010 <---> b

011 <---> bc

100 <---> a

101 <---> ac

110 <---> ab

111 <---> abc

思路出来了，代码也比较好写，分享一下我的代码：

/** 
 * Write a method that returns all subsets of a set 
 */  
  
#include   
#include   
#include   
  
/** 
 * 通过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;  
}

从n中选m个数

这里分为两种方法：递归和回溯

递归

递归思路如下，从n个数中取出m个数，可以分解为以下两步：

从n个数中选取编号最大的数，然后在剩下的n-1个数中选取m-1个数。直到从n-(m-1)中选取一个数为止

从n个数中选取次小的数，重复1的操作

代码如下：

/** 
 * 递归法解决组合问题 
 */  
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);  
        }  
    }  
}

回溯

暂时不会，谁给思路可以评论指导我以下