Combinations of a string using Recursion(Modified Version)

roverphoenix 0 407 Views

A simple program to calculate combinations of a string using recursion, I have used a malloc string of size 100 , you can change it to whatever value you want. The author is currently working at Microsoft.

for eg if input string is abcd and you want all 3 letter combinations, the o/p would be

abc
abd
acd
bcd

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void Combinations(char string[],int stack[],int combLength,int leftIndex);
void ComputeCombinations(char string[]);
void DisplayStack(int stack[],int stringLength,char string[]);
 
int main()
{
    char *string;
    printf("\nEnter the string ..\n");
    string = (char *)malloc(100 * sizeof(char));
    if(!string)
    {
        printf("\nmemory allocation for string failed exiting ..\n");
        exit(1);                              
    }            
    gets(string);
    ComputeCombinations(string);
    return 0;
}

void ComputeCombinations(char string[])
{
    int stringLength = 0;
    int *stack;
    int index = 0;
    int combLength = 0;
    int combIndex = 0;
    stringLength = (int)strlen(string); 
   
    stack = (int *)calloc(stringLength,sizeof(int));
    if(!stack)
    {
        printf("\nmemory allocation for stack failed exiting ..\n\n");
        exit(1);                              
    }

    for(combIndex = 1;combIndex <= stringLength;combIndex++)
    {
        printf("\n %d letter combinations ...\n\n",combIndex);
        for(index = 0; index < stringLength;index++)
        {
            stack[0] = index;
            Combinations(string,stack,combIndex,index);       
        }
    }
 
    return;     
}
void Combinations(char string[],int stack[],int combLength,int leftIndex)
{
    static int stringLength = (int)strlen(string);
    static int riteIndex = stringLength;
    static int level = 0;

    //Initialiaze the left index	
    if(level == 0)
    {
        leftIndex = stack[0]+1;
    }
    
    //if the current depth of tree = combinations length then print & return
    if(level == combLength - 1)
    {
        DisplayStack(stack,combLength,string);
        return;
    }
    level++;

    //recurse from current index to end of string
    for(;leftIndex < riteIndex;)
    {
        stack[level] = leftIndex;
        leftIndex++;
        Combinations(string,stack,combLength,leftIndex);
    }
    level--;
}

void DisplayStack(int stack[],int stringLength,char string[])
{
    int index = 0;
    for(index = 0; index < stringLength;index++)
    {
        printf(" %c ",string[stack[index]]);
    }
    printf("\n");
}

Dani AI

Generated

Good backtracking idea from , and correctly called out error-handling issues. The posted implementation works for simple runs but is fragile and non-portable in several ways: it uses gets (unsafe), relies on static local initializers that depend on strlen (non-portable and ties the function to a single input), and keeps recursion state in a static level (makes the routine non-reentrant and hard to reason about). Also, allocated buffers are never freed and error messages go to stdout instead of stderr. Below are concise, practical fixes and a clearer recursion pattern you can drop into the thread.

Use safe input and check allocations:

char buf[256];
if (!fgets(buf, sizeof buf, stdin)) return 0;
buf[strcspn(buf, "\n")] = '\0';   /* strip newline */
size_t n = strlen(buf);
if (n == 0) return 0;

Prefer computing string length once in the caller and passing it into the recursion. Avoid static recursion state — pass the current depth and start index as parameters. A compact, correct backtracking routine:

static void combine(const char *s, size_t n, size_t k,
                    size_t start, size_t depth, int *stack)
{
    if (depth == k) {
        for (size_t i = 0; i < k; ++i) putchar(s[stack[i]]);
        putchar('\n');
        return;
    }
    for (size_t i = start; i <= n - (k - depth); ++i) {
        stack[depth] = (int)i;
        combine(s, n, k, i + 1, depth + 1, stack);
    }
}

Usage notes and troubleshooting

  • Validate k <= n before calling.
  • Allocate stack sized to k (not necessarily n) and free it after use.
  • Send errors with fprintf(stderr, "...") and return/exit with EXIT_FAILURE on fatal errors (as suggested).
  • If you need unique combinations from a string with repeated characters, sort the string first and skip equal characters during recursion.
  • For very large n consider iterative/bitmask generation or streaming output; recursion depth is k.

These changes keep the algorithm clear, portable, and safe while preserving the original backtracking approach.

Member Avatar for ~s.o.s~
~s.o.s~ 2,560 Failure as a human

Some constructive comments:

1. exit (0) means successful return from a function. In case of unsuccessful memory allocation use, exit (1) instead of exit (0)

2. Always send the errors to the error stream rather than the output stream. In most of the cases the error stream is the ouput stream ie your monitor, but in specific cases it can be a log file.

3. A lightweight way to add a newline rather than writing printf ("\n") ; is putchar ('\n') ; 4. According to the principles of Software Engineering, the less the parameters passed to the functions, the better the function is. If your passed parameters exceed 4, try to re analyze your design.
The number of parameters passed is directly proportional to the complexity of the function.

Member Avatar for roverphoenix
roverphoenix 0 Newbie Poster

email @ for any q's about the code

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Edit Preview