Recursion can be categorized into path-aware and path-unaware forms. Most tree-related recursions are path-aware. Fundamentally, recursion implements depth-first search (DFS). To solve problems recursively, treat the recursive function as a black box that handles a subproblem, then reuse it. Beginners often try to fully expand the recursion, which can lead to confusion. Instead, abstractly trust that the function solves the problem, then delve into its mechanics.

Recursion and backtracking are complementary. Backtracking natural occurs during recursion as state restoration. Understanding this as "restoring state" clarifies the concept.

Generating All Substrings of a String

Given a string, find all its substrings. For "abc", there are 8 substrings: "", "a", "b", "c", "ab", "ac", "bc", "abc". This is equivalent to finding all subsets of a set.

Define a recursive function generateSubsets that returns all subsets. For "abcd":

• Subsets including 'a' combined with subsets of "bcd".
• Subsets excluding 'a' combined with subsets of "bcd". Excluding 'a' requires backtracking to restore state.

import java.util.*;

public class SubstringGenerator {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.next();
        char[] characters = input.toCharArray();
        StringBuilder current = new StringBuilder();
        Set<String> resultSet = new HashSet<>();
        generateSubsets(characters, 0, current, resultSet);
        
        for (String subset : resultSet) {
            System.out.print(subset + "/ ");
        }
    }

    static void generateSubsets(char[] chars, int position, StringBuilder builder, Set<String> set) {
        if (position == chars.length) {
            set.add(builder.toString());
            return;
        }
        builder.append(chars[position]);
        generateSubsets(chars, position + 1, builder, set);
        builder.deleteCharAt(builder.length() - 1);
        generateSubsets(chars, position + 1, builder, set);
    }
}

The recursion builds strings via StringBuilder. Backtracking removes the last character to explore the exclude branch. An alternative uses a char array as a stack:

static String[] getSubstrings(String str) {
    char[] source = str.toCharArray();
    Set<String> unique = new HashSet<>();
    buildSubsets(source, 0, new char[source.length], 0, unique);
    return unique.toArray(new String[0]);
}

static void buildSubsets(char[] src, int idx, char[] path, int size, Set<String> set) {
    if (idx == src.length) {
        set.add(new String(path, 0, size));
    } else {
        path[size] = src[idx];
        buildSubsets(src, idx + 1, path, size + 1, set);
        buildSubsets(src, idx + 1, path, size, set);
    }
}

Subsets of an Array Without Duplicates

Similar to string subsets, but with integers and no duplicates.

import java.util.*;

class SubsetFinder {
    List<List<Integer>> subsets = new ArrayList<>();
    
    public List<List<Integer>> findSubsets(int[] numbers) {
        dfs(numbers, 0, new ArrayList<>());
        return subsets;
    }
    
    void dfs(int[] nums, int pos, List<Integer> current) {
        if (pos == nums.length) {
            subsets.add(new ArrayList<>(current));
        } else {
            current.add(nums[pos]);
            dfs(nums, pos + 1, current);
            current.remove(current.size() - 1);
            dfs(nums, pos + 1, current);
        }
    }
}

Subsets of an Array With Duplicates

Duplicates cause repeated subsets. Sorting enables duplicate elimination.

import java.util.*;

class SubsetWithDup {
    public List<List<Integer>> subsetsWithDup(int[] numbers) {
        Arrays.sort(numbers);
        List<List<Integer>> output = new ArrayList<>();
        explore(numbers, 0, new ArrayList<>(), output);
        return output;
    }
    
    void explore(int[] nums, int idx, List<Integer> path, List<List<Integer>> result) {
        if (idx == nums.length) {
            result.add(new ArrayList<>(path));
        } else {
            path.add(nums[idx]);
            explore(nums, idx + 1, path, result);
            path.remove(path.size() - 1);
            explore(nums, idx + 1, path, result);
        }
    }
}

A more efficient approach groups identical elements to prune branches. For sorted array [1,1,1,2,2], treat the three 1's as a group with counts 0 to 3.

import java.util.*;

class OptimizedSubsetDup {
    public List<List<Integer>> subsetsWithDup(int[] numbers) {
        Arrays.sort(numbers);
        List<List<Integer>> result = new ArrayList<>();
        generate(numbers, 0, new ArrayList<>(), result);
        return result;
    }
    
    void generate(int[] nums, int start, List<Integer> current, List<List<Integer>> res) {
        if (start == nums.length) {
            res.add(new ArrayList<>(current));
        } else {
            int next = start + 1;
            while (next < nums.length && nums[start] == nums[next]) next++;
            int groupSize = next - start;
            for (int count = 0; count <= groupSize; count++) {
                for (int i = 0; i < count; i++) current.add(nums[start]);
                generate(nums, next, current, res);
                for (int i = 0; i < count; i++) current.remove(current.size() - 1);
            }
        }
    }
}

Letter Case Permutation

Generate all strings by toggling letter cases.

import java.util.*;

class CasePermutation {
    public List<String> letterCasePermutation(String s) {
        List<String> permutations = new ArrayList<>();
        traverse(s.toCharArray(), 0, new StringBuilder(), permutations);
        return permutations;
    }
    
    void traverse(char[] chars, int pos, StringBuilder builder, List<String> result) {
        if (pos == chars.length) {
            result.add(builder.toString());
        } else if (Character.isDigit(chars[pos])) {
            builder.append(chars[pos]);
            traverse(chars, pos + 1, builder, result);
            builder.deleteCharAt(builder.length() - 1);
        } else {
            builder.append(Character.toLowerCase(chars[pos]));
            traverse(chars, pos + 1, builder, result);
            builder.deleteCharAt(builder.length() - 1);
            builder.append(Character.toUpperCase(chars[pos]));
            traverse(chars, pos + 1, builder, result);
            builder.deleteCharAt(builder.length() - 1);
        }
    }
}

Permutations Without Duplicates

Generate all permutations of distinct elemants.

import java.util.*;

class PermutationGenerator {
    public List<List<Integer>> permute(int[] numbers) {
        List<List<Integer>> allPerms = new ArrayList<>();
        generate(numbers, 0, allPerms);
        return allPerms;
    }
    
    void generate(int[] nums, int fixed, List<List<Integer>> output) {
        if (fixed == nums.length) {
            List<Integer> permutation = new ArrayList<>();
            for (int num : nums) permutation.add(num);
            output.add(permutation);
        } else {
            for (int i = fixed; i < nums.length; i++) {
                swap(nums, fixed, i);
                generate(nums, fixed + 1, output);
                swap(nums, fixed, i);
            }
        }
    }
    
    void swap(int[] arr, int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}

Permutations With Duplicates

Add duplicate checking during swapping.

import java.util.*;

class UniquePermutations {
    public List<List<Integer>> permuteUnique(int[] numbers) {
        List<List<Integer>> result = new ArrayList<>();
        compute(numbers, 0, result);
        return result;
    }
    
    void compute(int[] nums, int level, List<List<Integer>> res) {
        if (level == nums.length) {
            List<Integer> perm = new ArrayList<>();
            for (int n : nums) perm.add(n);
            res.add(perm);
        } else {
            Set<Integer> seen = new HashSet<>();
            for (int j = level; j < nums.length; j++) {
                if (!seen.contains(nums[j])) {
                    seen.add(nums[j]);
                    swap(nums, level, j);
                    compute(nums, level + 1, res);
                    swap(nums, level, j);
                }
            }
        }
    }
    
    void swap(int[] arr, int x, int y) {
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }
}