字符串中的回溯问题

22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

思路：
用 StringBuilder 暂存我们的结果，left 和 right 分别表示剩下的左括号和右括号还有多少。注意剪枝，当 left 大于 right 时直接返回。

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        if (n == 0) return res;
        StringBuilder sb = new StringBuilder();
        dfs(sb, n, n, res);
        return res;
    }
    public void dfs(StringBuilder sb, int left, int right, List<String> res) {
        if (left == 0 && right == 0) {
            res.add(sb.toString());
        }
        // 剪枝
        if (left > right) {
            return;
        }
        if (left > 0) {
            sb.append("(");
            dfs(sb, left-1, right, res);
            sb.deleteCharAt(sb.length()-1);
        }
        if (right > 0) {
            sb.append(")");
            dfs(sb, left, right-1, res);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}

练习：

17. 电话号码的字母组合

思路：
维护一个字符串数组作为字典，数组下标与元素的对应关系和手机按键数字与字母的映射关系相同。用StringBuilder 暂存我们的结果，k 为当前数字索引，digits 为传入的数字字符串，res 存放最终结果。

784. 字母大小写全排列

思路：
传递一个参数 k 表示当前位置。按照小写、大写两种情况，对字符进行变换大小写处理。如果当前位置的字符不是字母，则将原字符串直接传入下一次调用中。不同于全排列、括号生成和电话号码的字母组合，这题中没有明显的回溯，而是不断派生出新的分支。