文字列のアルファベットの組み合わせ

0 1リュックサックの問題
まず文字列をリセットし、各文字に対応する個数を記録する.
組み合わせの結果をcomb(s,strCount,idx,aux)とし,sは重み付けされた文字列を表し,strCountは対応する個数を表し,idxは現在位置を表し,auxは現在位置がいくつ取ったかの数を表すとする.
comb(s,strCount,idx,aux)=aux[idx]がそれぞれ0の場合...n時comb(s,strCount,idx+1);

/*
 ============================================================================
 Name        : strCombination.c
 Author      : 
 Version     :
 Copyright   : 
 Description :                   aba   ：a b ab aa aab
 ============================================================================
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void pr_arrByAux(const char *s, int len,const int *aux)
{
	int i = 0, k = 0;
	for (i = 0; i < len; ++i)
	{
		for (k = 0; k < aux[i]; ++k)
			printf("%c", s[i]);
	}
	printf("
");
}
void pr_arr(const int *a,int len)
{
	int i=0;
	for(i=0;i<len;i++)
	{
		printf("%d ",a[i]);
	}
	printf("
");
}
//            ，            
//       s="aabbccd"
//       s="abcd"
//strCount 2,2,2,1
void delRepeatAndCount(char *s,int *strCount)
{
	char *pre,*p;
	int i=0;
	if(s==NULL || strlen(s) <= 1) return;
	pre=s,p=s+1;
	for(i=0;i<strlen(s);i++)
	{
		strCount[i]=1;
	}
	i=0;
	while(*p != '\0')
	{
		if(*p != *pre)
		{
			*(++pre)=*p++;
			++i;
		}
		else
		{
			++p;
			strCount[i]++;
		}
	}
	*(pre+1)='\0';
/*	pr_arr(strCount,strlen(s));
	puts(s);*/
}
int comp(const void *pa,const void *pb)
{
	return *(char*)pa - *(char*)pb;
}

//s          ，strCount          
void strCombination(const char *s, int len, int *strCount, int idx, int *aux)
{
	int i = 0;
	if (len < 1 || idx > len)		return;
	if (idx == len)
	{
		pr_arrByAux(s, len, aux);
		return;
	}
	aux[idx] = 0;
	for (i = 0; i <= strCount[idx]; ++i)
	{
		aux[idx] = i;
		strCombination(s, len, strCount, idx + 1, aux);
	}
	aux[idx] = 0;//  
}
//           
void strComb(const char *s)
{
	//strCount          
	int *aux,*strCount ,len;
	char *str; //       ，          
	if(s==NULL || strlen(s) < 1) return;
	//init
	len=strlen(s);
	aux=(int*)malloc(sizeof(int)*len);
	strCount=(int*)malloc(sizeof(int)*len);
	str=(char*)malloc(sizeof(char)*(len+1));
	strcpy(str,s);

	//kernel
	qsort(str,len,sizeof(char),comp); //       
	delRepeatAndCount(str,strCount); //  ，   
	strCombination(str,strlen(str),strCount,0,aux);//  

	//free
	free(str);
	free(strCount);
	free(aux);
}
int main(void)
{
	strComb("abaa");
	return 0;
}