String permutations and combinations

You're in a Google interview, and the interviewer asks you to generate every possible rearrangement of every possible subset of a string. It sounds like two separate problems mashed together, and that's exactly what it is. This problem, sometimes called "All Permutations of All Subsets" on other platforms, tests your ability to decompose a complex recursive problem into manageable pieces. Companies like Google, Facebook, and Twitter use it to evaluate how well candidates handle combinatorial explosion and recursive thinking.

TL;DR

Split the problem into two parts. First, generate all combinations (subsets) of the input string iteratively by starting with an empty string and progressively including each character. Then, for each non-empty combination, generate all its permutations recursively by peeling off the first character, permuting the remainder, and inserting the first character at every position. Collect everything into a set. The time complexity is O((2^n - 1) * (n * n!)) and the space complexity is O((2^n - 1) * (n!)).

Why This Problem Matters

This problem sits at the intersection of two fundamental concepts in computer science: combinations and permutations. Solving it requires you to implement both from scratch, which is exactly what interviewers want to see. It also forces you to think about how helper methods compose together, a skill that translates directly to building real production systems with clean, modular code.

Understanding the Problem

Given a string of unique characters, return a set containing all permutations of all combinations of those characters. For "AB", the combinations are "", "A", "B", and "AB". We discard the empty string, then permute each remaining combination. "A" and "B" have only one permutation each, while "AB" produces "AB" and "BA". The final result is {"A", "B", "AB", "BA"}.

For "ABC", the output contains 15 strings: single characters ("A", "B", "C"), all two-character permutations ("AB", "BA", "AC", "CA", "BC", "CB"), and all three-character permutations ("ABC", "ACB", "BAC", "BCA", "CAB", "CBA").

Constraints

• 1 ≤ n ≤ 15, where n is the length of the input string
• All characters in the input string are unique
• The output is a set, so ordering does not matter

The Two-Phase Strategy

The key to solving this cleanly is recognizing that it decomposes into two independent subproblems:

1. Combinations: Find all subsets of the input characters
2. Permutations: For each non-empty subset, find all of its rearrangements

Here is how the full algorithm flows for "AB":

The combinations method produces subsets, and the permutations method rearranges each one. The final output is the union of all permutation results.

Part 1: Building Combinations

The combinations algorithm is iterative and elegant. Start with a set containing only the empty string. For each character in the input, create new strings by appending that character to every string currently in the set, then add all new strings back.

For "AB":

Each character doubles the size of the set. Starting with 1 element, after processing "A" we have 2, and after "B" we have 4. In general, a string of length n produces 2^n combinations (including the empty string).

Here is the full expansion for "ABC":

After processing all three characters, we have 8 combinations. Remove the empty string and we're left with 7 non-empty subsets to permute.

private Set<String> combinations(String str) {
    Set<String> out = new HashSet<>(Set.of(""));
    for (int i = 0; i < str.length(); i++) {
        char c = str.charAt(i);
        Set<String> includeChar = out.stream()
                                    .map(item -> item + c)
                                    .collect(Collectors.toSet());
        out.addAll(includeChar);
    }
    return out;
}

The seed set {""} is important. Without it, there would be nothing to append the first character to, and the entire process would stall.

Part 2: Generating Permutations

The permutation algorithm is recursive. Given a string, peel off the first character and recursively permute the remainder. Then insert the first character at every valid position in each sub-permutation.

The recursion bottoms out when the string is empty (return an empty set) or when the remainder produces no permutations (return a set containing just the first character).

The recursion goes deeper until it hits the base case, then builds back up as each level inserts its character into the results from below.

The insertChar Helper

This is the workhorse that makes the permutation algorithm tick. Given a character c and a word, it produces every string formed by inserting c at each index from 0 through word.length.

For insertChar('A', "BC"), we get three results:

• Index 0: "A" + "BC" = "ABC"
• Index 1: "B" + "A" + "C" = "BAC"
• Index 2: "BC" + "A" = "BCA"

private Set<String> insertChar(char c, String word) {
    Set<String> out = new HashSet<>();
    for (int i = 0; i <= word.length(); i++) {
        String left = word.substring(0, i);
        String right = word.substring(i);
        out.add(left + c + right);
    }
    return out;
}

Permutations in Action

Here is the complete flow for permutations("AB"):

The recursion peels off "A", discovers that permutations("B") returns {"B"}, then calls insertChar('A', "B") to produce {"AB", "BA"}.

private Set<String> permutations(String str) {
    if (str.isEmpty()) return new HashSet<>();
    char first = str.charAt(0);
    String remainder = str.substring(1);
    Set<String> remainderPermutations = permutations(remainder);
    if (remainderPermutations.isEmpty()) return Set.of(String.valueOf(first));
    return remainderPermutations
             .stream()
             .flatMap(word -> insertChar(first, word).stream())
             .collect(Collectors.toSet());
}

Putting It All Together

Prefer a different language? Jump to solutions in other languages.

The main method connects the two phases with Java streams. It calls combinations, then flat-maps each combination through permutations, and collects the results into a set. The empty string from the combinations output produces an empty set of permutations, so it drops out naturally.

import java.util.HashSet;
import java.util.Set;
import java.util.stream.Collectors;

public class Solution {
  public Set<String> permAndComb(String str) {
    return combinations(str)
             .stream()
             .flatMap(s -> permutations(s).stream())
             .collect(Collectors.toSet());
  }

  private Set<String> combinations(String str) {
    Set<String> out = new HashSet<>(Set.of(""));
    for (int i = 0; i < str.length(); i++) {
      char c = str.charAt(i);
      Set<String> includeChar = out.stream()
                                  .map(item -> item + c)
                                  .collect(Collectors.toSet());
      out.addAll(includeChar);
    }
    return out;
  }

  private Set<String> permutations(String str) {
    if (str.isEmpty()) return new HashSet<>();
    char first = str.charAt(0);
    String remainder = str.substring(1);
    Set<String> remainderPermutations = permutations(remainder);
    if (remainderPermutations.isEmpty()) return Set.of(String.valueOf(first));
    return remainderPermutations
             .stream()
             .flatMap(word -> insertChar(first, word).stream())
             .collect(Collectors.toSet());
  }

  private Set<String> insertChar(char c, String word) {
    Set<String> out = new HashSet<>();
    for (int i = 0; i <= word.length(); i++) {
      String left = word.substring(0, i);
      String right = word.substring(i);
      out.add(left + c + right);
    }
    return out;
  }
}

Complexity Analysis

Time Complexity: O((2^n - 1) * (n * n!))

There are 2^n - 1 non-empty combinations. For each combination of length k, generating its permutations takes O(k * k!) time since there are k! permutations and each requires O(k) work for string construction. The dominant cost comes from the longest combinations, where k approaches n, giving us the O(n * n!) factor per combination.

Space Complexity: O((2^n - 1) * (n!))

The output set stores every permutation of every combination. The number of strings in the output is the sum of k! for k from 1 to n, weighted by the binomial coefficient C(n, k). In practice, the space is dominated by the full-length permutations, of which there are n!.

For the constraint n ≤ 15, the output can grow very large. With n = 15, there are 15! = 1,307,674,368,000 permutations of the full string alone, though in practice the algorithm would be tested with much smaller inputs.

Common Pitfalls

1. Forgetting the seed empty string in combinations. Without "" in the initial set, the first character has nothing to append to and you get zero combinations.

2. Mutating the set while iterating. Creating includeChar as a separate set before calling addAll avoids ConcurrentModificationException. If you tried to add elements directly during the stream operation, Java would throw.

3. Missing the base case for single characters. When remainderPermutations is empty but first exists, you need to return Set.of(String.valueOf(first)) rather than an empty set. Without this, single-character strings would never appear in the output.

4. Confusing combinations with permutations. The combinations step generates subsets where order does not matter ("AB" and "BA" are the same combination). The permutations step then rearranges each subset. Mixing up the two leads to either missing results or duplicates.

Interview Tips

When presenting this solution:

1. Start by decomposing the problem. Explain that you'll solve combinations and permutations separately, then compose them. This shows structured thinking.

2. Trace through a small example first. Use "AB" to walk through both helpers before coding. Write out the combinations set at each step and the permutation recursion tree.

3. Discuss the complexity upfront. Acknowledge that the output is exponentially large. Interviewers appreciate candidates who recognize the inherent complexity of combinatorial problems rather than trying to optimize what cannot be optimized.

4. Mention the constraint on unique characters. Point out that the algorithm relies on character uniqueness and explain how you would adapt it for duplicates (sorting and skipping equal characters).

Key Takeaways

• Decomposing a complex combinatorial problem into independent subproblems (combinations, then permutations) makes the code modular and easier to reason about.
• The iterative combination approach doubles the set size with each character, producing 2^n subsets in O(2^n) time.
• The recursive permutation approach peels off one character, recurses on the remainder, then uses insertChar to place the character at every position, producing k! permutations for a string of length k.
• The total output size grows exponentially with n, and no algorithmic optimization can avoid this since every result must be explicitly generated.
• Seed the combinations set with the empty string so the first character has something to append to. Missing this initialization is the most common bug.

Related Problems and Practice

Once you're comfortable with this problem, these related challenges build on the same recursive and combinatorial foundations:

• Recursive String Permutations (Problem 95) focuses on just the permutations half
• Power Set Exploration (Problem 225) is pure subset/combination generation
• Generate Combinations of Parentheses (Problem 61) applies recursion with constraints
• Sum Combinations with Repeats (Problem 186) adds a target-sum twist to combination generation

This problem and hundreds of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed roles at top tech companies. Practice these patterns regularly and the recursive decomposition will become second nature.

Solutions in Other Languages

Python

from typing import List, Set


class Solution:
    def perm_and_comb(self, s: str) -> Set[str]:
        return set([item for
                    sublist in
                    [self.permutations(w) for w in self.combinations(s)]
                    for item in sublist])

    def combinations(self, s: str) -> List[str]:
        out = [""]
        for i in range(0, len(s)):
            c = s[i]
            include_char = [item + c for item in out]
            for word in include_char:
                out.append(word)
        return out

    def permutations(self, s: str) -> List[str]:
        if len(s) == 0:
            return []
        first, remainder = s[0], s[1:]
        remainder_permutations = self.permutations(remainder)
        if len(remainder_permutations) == 0:
            return [first]
        return [item for
                sublist in
                [self.insert_char(first, w) for w in remainder_permutations]
                for item in sublist]

    def insert_char(self, c: str, word: str) -> List[str]:
        out = []
        for i in range(0, len(word) + 1):
            left, right = word[0:i], word[i:]
            out.append(left + c + right)
        return out

JavaScript

class Solution {
  permAndComb(str) {
    return new Set(
      this.combinations(str)
        .flatMap(combination => this.permutations(combination))
    );
  }

  combinations(str) {
    let out = [""];
    for (let i = 0; i < str.length; i++) {
      const c = str.charAt(i);
      const includeChar = out.map(item => item + c);
      includeChar.forEach(s => out = out.concat(s));
    }
    return out;
  }

  permutations(str) {
    if (str.length === 0) return [];
    const first = str.charAt(0);
    const remainder = str.substring(1);
    const remainderPermutations = this.permutations(remainder);
    if (remainderPermutations.length === 0) return [first];
    return remainderPermutations.flatMap(word => this.insertChar(first, word));
  }

  insertChar(c, word) {
    const out = [];
    for (let i = 0; i <= word.length; i++) {
      const left = word.substring(0, i);
      const right = word.substring(i);
      out.push(left + c + right);
    }
    return out;
  }
}

TypeScript

class Solution {
  permAndComb(str: string): Set<string> {
    return new Set(
      this.combinations(str)
        .flatMap(combination => this.permutations(combination))
    );
  }

  private combinations(str: string): string[] {
    let out: string[] = [""];
    for (let i = 0; i < str.length; i++) {
      const c = str.charAt(i);
      const includeChar = out.map(item => item + c);
      includeChar.forEach(s => out = out.concat(s));
    }
    return out;
  }

  private permutations(str: string): string[] {
    if (str.length === 0) return [];
    const first = str.charAt(0);
    const remainder = str.substring(1);
    const remainderPermutations = this.permutations(remainder);
    if (remainderPermutations.length === 0) return [first];
    return remainderPermutations.flatMap(word => this.insertChar(first, word));
  }

  private insertChar(c: string, word: string): string[] {
    const out: string[] = [];
    for (let i = 0; i <= word.length; i++) {
      const left = word.substring(0, i);
      const right = word.substring(i);
      out.push(left + c + right);
    }
    return out;
  }
}

C++

#include <iostream>
#include <unordered_set>
#include <vector>

class Solution {
public:
  std::unordered_set<std::string> permAndComb(const std::string &str) {
    std::unordered_set<std::string> comb = combinations(str);
    std::unordered_set<std::string> perm;
    for (auto const &s: comb) {
      std::unordered_set<std::string> permStr = permutations(s);
      perm.insert(permStr.begin(), permStr.end());
    }
    return perm;
  }

private:
  std::unordered_set<std::string> combinations(const std::string &str) {
    std::unordered_set<std::string> out;
    out.insert("");
    for (size_t i = 0; i < str.length(); i++) {
      char c = str[i];
      std::unordered_set<std::string> includeChar;
      for (const auto &item : out) {
        includeChar.insert(item + c);
      }
      out.insert(includeChar.begin(), includeChar.end());
    }
    return out;
  }

  std::unordered_set<std::string> permutations(const std::string &str) {
    if (str.empty()) return {};
    char first = str[0];
    std::string remainder = str.substr(1);
    std::unordered_set<std::string> remainderPermutations = permutations(remainder);
    if (remainderPermutations.empty()) return {std::string(1, first)};
    std::unordered_set<std::string> result;
    for (const auto &word : remainderPermutations) {
      std::vector<std::string> inserted = insertChar(first, word);
      result.insert(inserted.begin(), inserted.end());
    }
    return result;
  }

  std::vector<std::string> insertChar(char c, const std::string &word) {
    std::vector<std::string> out;
    for (size_t i = 0; i <= word.length(); i++) {
      std::string left = word.substr(0, i);
      std::string right = word.substr(i);
      out.push_back(left + c + right);
    }
    return out;
  }
};

Go

package solution

func (s *Solution) PermAndComb(str string) map[string]bool {
    comb := combinations(str)
    perm := make(map[string]bool)
    for s := range comb {
        for permStr := range permutations(s) {
            perm[permStr] = true
        }
    }
    return perm
}

func combinations(str string) map[string]bool {
    out := make(map[string]bool)
    out[""] = true
    for i := 0; i < len(str); i++ {
        includeChar := make(map[string]bool)
        for o := range out {
            includeChar[o+string(str[i])] = true
        }
        for ic := range includeChar {
            out[ic] = true
        }
    }
    return out
}

func permutations(str string) map[string]bool {
    if len(str) == 0 {
        return make(map[string]bool)
    }
    first, remainder := string(str[0]), str[1:]
    remainderPermutations := permutations(remainder)
    if len(remainderPermutations) == 0 {
        return map[string]bool{first: true}
    }
    result := make(map[string]bool)
    for word := range remainderPermutations {
        for _, newWord := range insertChar(first, word) {
            result[newWord] = true
        }
    }
    return result
}

func insertChar(c, word string) []string {
    var out []string
    for i := 0; i <= len(word); i++ {
        left, right := word[:i], word[i:]
        out = append(out, left+c+right)
    }
    return out
}

Go uses map[string]bool as an idiomatic set since the language has no built-in set type.

Scala

import scala.collection.mutable

class Solution {
  def permAndComb(str: String): Set[String] = {
    combinations(str).flatMap(permutations)
  }

  private def combinations(str: String): Set[String] = {
    val out: mutable.Set[String] = mutable.Set("")
    for (i <- 0 until str.length) {
      val includeChar = out.map(prefix => prefix + str.charAt(i))
      out.addAll(includeChar)
    }
    out.toSet
  }

  private def permutations(str: String): Set[String] = {
    if (str.isEmpty) Set.empty[String]
    else {
      val first = str.charAt(0)
      val remainder = str.substring(1)
      val remainderPermutations = permutations(remainder)
      if (remainderPermutations.isEmpty) return Set(first.toString)
      remainderPermutations.flatMap(insertChar(first, _))
    }
  }

  private def insertChar(c: Char, word: String): Set[String] = {
    val out = mutable.Set[String]()
    for (i <- 0 to word.length) {
      val left = word.substring(0, i)
      val right = word.substring(i)
      out.add(left + c + right)
    }
    out.toSet
  }
}

Scala's flatMap on a set composes the combinations-then-permutations pipeline in a single expression.

Kotlin

class Solution {
    fun permAndComb(str: String): Set<String> {
        return combinations(str)
            .flatMap { s -> permutations(s) }
            .toSet()
    }

    private fun combinations(str: String): Set<String> {
        val out = mutableSetOf("")
        for (i in 0 until str.length) {
            val c = str[i]
            val includeChar = out.map { item -> item + c }.toSet()
            out.addAll(includeChar)
        }
        return out
    }

    private fun permutations(str: String): Set<String> {
        if (str.isEmpty()) return emptySet()
        val first = str[0]
        val remainder = str.substring(1)
        val remainderPermutations = permutations(remainder)
        if (remainderPermutations.isEmpty()) return setOf(first.toString())
        return remainderPermutations
            .flatMap { word -> insertChar(first, word) }
            .toSet()
    }

    private fun insertChar(c: Char, word: String): Set<String> {
        val out = mutableSetOf<String>()
        for (i in 0..word.length) {
            val left = word.substring(0, i)
            val right = word.substring(i)
            out.add(left + c + right)
        }
        return out
    }
}

Ruby

class Solution
  def perm_and_comb(str)
    combinations(str).flat_map { |w| permutations(w) }.to_set
  end

  private

  def combinations(str)
    out = Set.new([""])
    str.each_char do |c|
      include_char = out.map { |item| item + c }
      out.merge(include_char)
    end
    out
  end

  def permutations(str)
    return Set.new if str.empty?
    first = str[0]
    remainder = str[1..]
    remainder_permutations = permutations(remainder)
    return Set.new([first]) if remainder_permutations.empty?
    remainder_permutations.flat_map { |word| insert_char(first, word) }.to_set
  end

  def insert_char(c, word)
    (0..word.length).map do |i|
      left = word[0...i]
      right = word[i..]
      left + c + right
    end
  end
end

Rust

use std::collections::HashSet;

impl Solution {
    pub fn perm_and_comb(&self, s: &str) -> HashSet<String> {
        let comb = Self::combinations(s);
        let mut result = HashSet::new();
        for c in &comb {
            for p in Self::permutations(c) {
                result.insert(p);
            }
        }
        result
    }

    fn combinations(s: &str) -> HashSet<String> {
        let mut out = HashSet::new();
        out.insert(String::new());
        for c in s.chars() {
            let include_char: HashSet<String> = out.iter()
                .map(|item| format!("{}{}", item, c))
                .collect();
            for item in include_char {
                out.insert(item);
            }
        }
        out
    }

    fn permutations(s: &str) -> HashSet<String> {
        if s.is_empty() {
            return HashSet::new();
        }
        let first = &s[..1];
        let remainder = &s[1..];
        let remainder_perms = Self::permutations(remainder);
        if remainder_perms.is_empty() {
            let mut set = HashSet::new();
            set.insert(first.to_string());
            return set;
        }
        let mut result = HashSet::new();
        for word in &remainder_perms {
            for inserted in Self::insert_char(first, word) {
                result.insert(inserted);
            }
        }
        result
    }

    fn insert_char(c: &str, word: &str) -> Vec<String> {
        let mut out = Vec::new();
        for i in 0..=word.len() {
            let left = &word[..i];
            let right = &word[i..];
            out.push(format!("{}{}{}", left, c, right));
        }
        out
    }
}

Swift

class Solution {
    func permAndComb(_ str: String) -> Set<String> {
        let comb = combinations(str)
        var result = Set<String>()
        for s in comb {
            for p in permutations(s) {
                result.insert(p)
            }
        }
        return result
    }

    private func combinations(_ str: String) -> Set<String> {
        var out: Set<String> = [""]
        for c in str {
            let includeChar = out.map { $0 + String(c) }
            for item in includeChar {
                out.insert(item)
            }
        }
        return out
    }

    private func permutations(_ str: String) -> Set<String> {
        if str.isEmpty { return Set() }
        let first = String(str.first!)
        let remainder = String(str.dropFirst())
        let remainderPermutations = permutations(remainder)
        if remainderPermutations.isEmpty { return Set([first]) }
        var result = Set<String>()
        for word in remainderPermutations {
            for inserted in insertChar(first, word) {
                result.insert(inserted)
            }
        }
        return result
    }

    private func insertChar(_ c: String, _ word: String) -> [String] {
        var out = [String]()
        for i in 0...word.count {
            let index = word.index(word.startIndex, offsetBy: i)
            let left = String(word[..<index])
            let right = String(word[index...])
            out.append(left + c + right)
        }
        return out
    }
}

C#

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public HashSet<string> PermAndComb(string str) {
        var comb = Combinations(str);
        var result = new HashSet<string>();
        foreach (var s in comb) {
            foreach (var p in Permutations(s)) {
                result.Add(p);
            }
        }
        return result;
    }

    private HashSet<string> Combinations(string str) {
        var outSet = new HashSet<string> { "" };
        foreach (char c in str) {
            var includeChar = outSet.Select(item => item + c).ToList();
            foreach (var item in includeChar) {
                outSet.Add(item);
            }
        }
        return outSet;
    }

    private HashSet<string> Permutations(string str) {
        if (str.Length == 0) return new HashSet<string>();
        char first = str[0];
        string remainder = str.Substring(1);
        var remainderPerms = Permutations(remainder);
        if (remainderPerms.Count == 0) return new HashSet<string> { first.ToString() };
        var result = new HashSet<string>();
        foreach (var word in remainderPerms) {
            foreach (var inserted in InsertChar(first, word)) {
                result.Add(inserted);
            }
        }
        return result;
    }

    private List<string> InsertChar(char c, string word) {
        var outList = new List<string>();
        for (int i = 0; i <= word.Length; i++) {
            string left = word.Substring(0, i);
            string right = word.Substring(i);
            outList.Add(left + c + right);
        }
        return outList;
    }
}

Dart

class Solution {
  Set<String> permAndComb(String str) {
    final comb = combinations(str);
    final result = <String>{};
    for (final s in comb) {
      result.addAll(permutations(s));
    }
    return result;
  }

  Set<String> combinations(String str) {
    final out = <String>{""};
    for (int i = 0; i < str.length; i++) {
      final c = str[i];
      final includeChar = out.map((item) => item + c).toSet();
      out.addAll(includeChar);
    }
    return out;
  }

  Set<String> permutations(String str) {
    if (str.isEmpty) return {};
    final first = str[0];
    final remainder = str.substring(1);
    final remainderPerms = permutations(remainder);
    if (remainderPerms.isEmpty) return {first};
    final result = <String>{};
    for (final word in remainderPerms) {
      result.addAll(insertChar(first, word));
    }
    return result;
  }

  List<String> insertChar(String c, String word) {
    final out = <String>[];
    for (int i = 0; i <= word.length; i++) {
      final left = word.substring(0, i);
      final right = word.substring(i);
      out.add(left + c + right);
    }
    return out;
  }
}

PHP

class Solution {
    function permAndComb($str) {
        $comb = $this->combinations($str);
        $result = [];
        foreach ($comb as $s) {
            $result = array_merge($result, $this->permutations($s));
        }
        return array_values(array_unique($result));
    }

    private function combinations($str) {
        $out = [""];
        for ($i = 0; $i < strlen($str); $i++) {
            $c = $str[$i];
            $includeChar = array_map(function($item) use ($c) {
                return $item . $c;
            }, $out);
            $out = array_merge($out, $includeChar);
        }
        return $out;
    }

    private function permutations($str) {
        if (strlen($str) === 0) return [];
        $first = $str[0];
        $remainder = substr($str, 1);
        $remainderPerms = $this->permutations($remainder);
        if (empty($remainderPerms)) return [$first];
        $result = [];
        foreach ($remainderPerms as $word) {
            $result = array_merge($result, $this->insertChar($first, $word));
        }
        return $result;
    }

    private function insertChar($c, $word) {
        $out = [];
        for ($i = 0; $i <= strlen($word); $i++) {
            $left = substr($word, 0, $i);
            $right = substr($word, $i);
            $out[] = $left . $c . $right;
        }
        return $out;
    }
}