Program to Generate All Combinations of a Given String in All Programming Languages

Master the art of generating string combinations with implementations in Python, JavaScript, Java, C, C++, PHP, and Go. Learn with code examples, time complexity, and space analysis.

Generating all combinations (or permutations) of a given string is a popular coding interview question. This problem tests your understanding of recursion, backtracking, and data structures. Let’s explore how to solve it efficiently using different programming languages

Understanding Permutations

Permutations involve arranging all characters of a string in every possible order. For a string of length nnn, the total number of permutations is n!n!n!.

Examples:

• Input: "abc"
  Output: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
• Input: "ab"
  Output: ['ab', 'ba']

Approach to Solve the Problem

The standard way to solve this is through recursion with backtracking.

Recursive Backtracking Algorithm:

1. Start with the first character and swap it with every other character.
2. Repeat the process for the remaining substring.
3. Backtrack to restore the original state after each swap.

Algorithm Explanation

Here’s a high-level pseudocode:

function permutations(string, currentIndex):
    if currentIndex == length of string:
        print string
        return
    for i = currentIndex to length of string:
        swap(string[currentIndex], string[i])
        permutations(string, currentIndex + 1)
        swap(string[currentIndex], string[i])  # Backtrack

Time and Space Complexity

• Time Complexity: O(n!), as there are n! permutations for a string of length n.
• Space Complexity: O(n), due to the recursion stack.

Implementation in Multiple Programming Languages

Python

def permutations(s, step=0):
    if step == len(s):
        print("".join(s))
    for i in range(step, len(s)):
        s[step], s[i] = s[i], s[step]  # Swap
        permutations(s, step + 1)
        s[step], s[i] = s[i], s[step]  # Backtrack

# Test case
permutations(list("abc"))

JavaScript

function permutations(s, step = 0) {
    if (step === s.length) {
        console.log(s.join(""));
    }
    for (let i = step; i < s.length; i++) {
        [s[step], s[i]] = [s[i], s[step]]; // Swap
        permutations(s, step + 1);
        [s[step], s[i]] = [s[i], s[step]]; // Backtrack
    }
}

// Test case
permutations([... "abc"]);

Java

import java.util.*;

public class StringPermutations {
    public static void permute(char[] s, int step) {
        if (step == s.length) {
            System.out.println(new String(s));
        }
        for (int i = step; i < s.length; i++) {
            swap(s, step, i);
            permute(s, step + 1);
            swap(s, step, i); // Backtrack
        }
    }

    private static void swap(char[] s, int i, int j) {
        char temp = s[i];
        s[i] = s[j];
        s[j] = temp;
    }

    public static void main(String[] args) {
        permute("abc".toCharArray(), 0);
    }
}

PHP

function permutations($s, $step = 0) {
    if ($step == strlen($s)) {
        echo $s . "\n";
    }
    for ($i = $step; $i < strlen($s); $i++) {
        $s = swap($s, $step, $i);
        permutations($s, $step + 1);
        $s = swap($s, $step, $i); // Backtrack
    }
}

function swap($s, $i, $j) {
    $arr = str_split($s);
    $temp = $arr[$i];
    $arr[$i] = $arr[$j];
    $arr[$j] = $temp;
    return implode("", $arr);
}

permutations("abc");

C++

#include <iostream>
#include <string>
using namespace std;

void permutations(string s, int step) {
    if (step == s.size()) {
        cout << s << endl;
        return;
    }
    for (int i = step; i < s.size(); i++) {
        swap(s[step], s[i]);
        permutations(s, step + 1);
        swap(s[step], s[i]); // Backtrack
    }
}

int main() {
    permutations("abc", 0);
    return 0;
}

C

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

void swap(char* x, char* y) {
    char temp = *x;
    *x = *y;
    *y = temp;
}

void permutations(char* s, int step, int len) {
    if (step == len) {
        printf("%s\n", s);
        return;
    }
    for (int i = step; i < len; i++) {
        swap(&s[step], &s[i]);
        permutations(s, step + 1, len);
        swap(&s[step], &s[i]); // Backtrack
    }
}

int main() {
    char s[] = "abc";
    permutations(s, 0, strlen(s));
    return 0;
}

Go

package main

import "fmt"

func permutations(s []rune, step int) {
    if step == len(s) {
        fmt.Println(string(s))
        return
    }
    for i := step; i < len(s); i++ {
        s[step], s[i] = s[i], s[step] // Swap
        permutations(s, step+1)
        s[step], s[i] = s[i], s[step] // Backtrack
    }
}

func main() {
    permutations([]rune("abc"), 0)
}

Edge Cases to Consider

• Empty String: Return an empty list.
• Single Character String: Only one permutation exists.
• Duplicate Characters: Handle duplicates gracefully to avoid redundant outputs.

Applications of String Permutations

• Password Generation: Generates all possible variations for password cracking.
• Word Scrambles: Useful in games and puzzles.
• Algorithmic Problem-Solving: Core component in brute-force solutions.

FAQs

Why use recursion for permutations?
Recursion simplifies the process by breaking the problem into smaller, manageable steps.

How to optimize for large strings?
Use caching to avoid redundant computations or consider iterative methods.

How does the algorithm handle duplicate characters?
Add logic to skip repeated swaps for duplicate characters.

Can permutations be used in real-world applications?
Yes, in cryptography, data analysis, and more.

What’s the difference between combinations and permutations?
Combinations don’t consider order, while permutations do.