Tree Recursion

All Combinations

Number of ways to pick [0,n] items. For every item i in n we have 2 decisions to make

1. Select
2. Ignore

Which totals to ${2}^{n}$.

Example: Number of ways to pick a, b, c is 8

    <empty>
    a
    b
    c
    ab
    ac
    bc
    abc

private static void combinations(List<Character> chars, List<String> result, String s, int idx) {
    if (idx == chars.size()) {
        result.add(s);
        return;
    }

    combinations(chars, result, s+"", idx+1);
    combinations(chars, result, s+chars.get(idx), idx+1);
}

Permutation

Number of ways to arrange n items is equal to n x n-1 x n-2...1 which is equal to n! Example: In how many ways can we arrange a string abc? For the 1st position we have 3 options, 2nd position 2 and 3rd Position 3. Totalling, 3x2x1 = 3!

    abc
    acb
    bac
    bca
    cba
    cab

private static List<String> permutePostOrder(Set<Character> chars) {
    if(chars.isEmpty()) {
        return new ArrayList<>();
    }

    List<String> result = new ArrayList<>();
    for (char c : chars) {
        List<String> subset = permutePostOrder(chars.stream().filter(ch -> ch != c).collect(Collectors.toSet()));
        if (subset.isEmpty()) {
            result.add(String.valueOf(c));
        } else {
            subset.forEach(r -> result.add(r + c));
        }
    }
    return result;
}

Partial Permutation

nPr Number of ways to arrange r items out of n. Which is equal to $\frac{n!}{(n-r)!}$

    ab
    ac
    bc

private static List<String> partialPermutePostOrder(Set<Character> chars, int r) {
    if(r == 0 || chars.isEmpty()) {
        return new ArrayList<>();
    }

    List<String> result = new ArrayList<>();
    for (char c : chars) {
        List<String> subset = partialPermutePostOrder(chars.stream().filter(ch -> ch != c).collect(Collectors.toSet()), r-1);
        if (subset.isEmpty()) {
            result.add(String.valueOf(c));
        } else {
            subset.forEach(sub-> result.add(sub + c));
        }
    }

    return result;
}

Combination

Similar to partial permutation but repetitions aren't allowed, only unique combinations are considered. nCr Number of ways to arrange r items out of n. Which is equal to $\frac{n!}{(n-r)!r!}$