String backtracking

1static List<String> generateParentheses(int n) {
2    List<String> out = new ArrayList<>();
3    gen(0, 0, n, new StringBuilder(), out);
4    return out;
5}
6private static void gen(int open, int close, int n, StringBuilder sb, List<String> out) {
7    if (sb.length() == 2 * n) { out.add(sb.toString()); return; }
8    if (open < n) { sb.append('('); gen(open + 1, close, n, sb, out); sb.deleteCharAt(sb.length() - 1); }
9    if (close < open) { sb.append(')'); gen(open, close + 1, n, sb, out); sb.deleteCharAt(sb.length() - 1); }
10}

1static List<List<String>> partitionPalindromes(String s) {
2    List<List<String>> out = new ArrayList<>();
3    cut(s, 0, new ArrayList<>(), out);
4    return out;
5}
6private static void cut(String s, int start, List<String> path, List<List<String>> out) {
7    if (start == s.length()) { out.add(new ArrayList<>(path)); return; }
8    for (int end = start + 1; end <= s.length(); end++) {
9        if (!isPal(s, start, end - 1)) continue;                // prune: only palindromic pieces
10        path.add(s.substring(start, end));
11        cut(s, end, path, out);
12        path.remove(path.size() - 1);
13    }
14}
15private static boolean isPal(String s, int i, int j) {
16    while (i < j) if (s.charAt(i++) != s.charAt(j--)) return false;
17    return true;
18}

1static final String[] LETTERS = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
2
3static List<String> letterCombinations(String digits) {
4    List<String> out = new ArrayList<>();
5    if (digits.isEmpty()) return out;
6    spell(digits, 0, new StringBuilder(), out);
7    return out;
8}
9private static void spell(String digits, int i, StringBuilder sb, List<String> out) {
10    if (i == digits.length()) { out.add(sb.toString()); return; }
11    for (char c : LETTERS[digits.charAt(i) - '0'].toCharArray()) {
12        sb.append(c);
13        spell(digits, i + 1, sb, out);
14        sb.deleteCharAt(sb.length() - 1);
15    }
16}

1static List<String> restoreIp(String s) {
2    List<String> out = new ArrayList<>();
3    segment(s, 0, new ArrayList<>(), out);
4    return out;
5}
6private static void segment(String s, int start, List<String> parts, List<String> out) {
7    if (parts.size() == 4) {
8        if (start == s.length()) out.add(String.join(".", parts));     // used every digit
9        return;
10    }
11    for (int len = 1; len <= 3 && start + len <= s.length(); len++) {
12        String seg = s.substring(start, start + len);
13        if ((seg.length() > 1 && seg.charAt(0) == '0') || Integer.parseInt(seg) > 255) continue;   // invalid segment
14        parts.add(seg);
15        segment(s, start + len, parts, out);
16        parts.remove(parts.size() - 1);
17    }
18}

1static List<String> wordBreak(String s, Set<String> dict) {
2    List<String> out = new ArrayList<>();
3    split(s, 0, dict, new ArrayList<>(), out);
4    return out;
5}
6private static void split(String s, int start, Set<String> dict, List<String> words, List<String> out) {
7    if (start == s.length()) { out.add(String.join(" ", words)); return; }
8    for (int end = start + 1; end <= s.length(); end++) {
9        String word = s.substring(start, end);
10        if (!dict.contains(word)) continue;                     // prune: only dictionary words
11        words.add(word);
12        split(s, end, dict, words, out);
13        words.remove(words.size() - 1);
14    }
15}