运用回溯算法，解决排列、组合和子集问题

回溯算法本质上也是一种暴力穷举算法，可以理解为：每个回溯问题就是遍历一个决策树的过程，每个叶子节点都存在一个数值，寻找叶子结点是否为满足条件的值，然后收集全部满足条件的值的过程就是回溯算法。

排列、组合和子集问题，无非就是寻找决策树叶子节点的过程，只是这三个问题对树枝的遍历和剪/加树枝有稍微变化罢了，然后在区分一下三种边界条件：元素无重复不可复选、元素无重复可复选、元素可重复不可复选。

回溯算法框架

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

形式一、元素无重不可复选，即 nums 中的元素都是唯一的，每个元素最多只能被使用一次，backtrack 核心代码如下：

/* 组合/子集问题回溯算法框架 */
void backtrack(int[] nums, int start) {
    // 回溯算法标准框架
    for (int i = start; i < nums.length; i++) {
        // 做选择
        track.addLast(nums[i]);
        // 注意参数
        backtrack(nums, i + 1);
        // 撤销选择
        track.removeLast();
    }
}

/* 排列问题回溯算法框架 */
void backtrack(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        // 剪枝逻辑
        if (used[i]) {
            continue;
        }
        // 做选择
        used[i] = true;
        track.addLast(nums[i]);

        backtrack(nums);
        // 撤销选择
        track.removeLast();
        used[i] = false;
    }
}

形式二、元素可重不可复选，即 nums 中的元素可以存在重复，每个元素最多只能被使用一次，其关键在于排序和剪枝，backtrack 核心代码如下：

Arrays.sort(nums);
/* 组合/子集问题回溯算法框架 */
void backtrack(int[] nums, int start) {
    // 回溯算法标准框架
    for (int i = start; i < nums.length; i++) {
        // 剪枝逻辑，跳过值相同的相邻树枝
        if (i > start && nums[i] == nums[i - 1]) {
            continue;
        }
        // 做选择
        track.addLast(nums[i]);
        // 注意参数
        backtrack(nums, i + 1);
        // 撤销选择
        track.removeLast();
    }
}


Arrays.sort(nums);
/* 排列问题回溯算法框架 */
void backtrack(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        // 剪枝逻辑
        if (used[i]) {
            continue;
        }
        // 剪枝逻辑，固定相同的元素在排列中的相对位置
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
            continue;
        }
        // 做选择
        used[i] = true;
        track.addLast(nums[i]);

        backtrack(nums);
        // 撤销选择
        track.removeLast();
        used[i] = false;
    }
}

形式三、元素无重可复选，即 nums 中的元素都是唯一的，每个元素可以被使用若干次，只要删掉去重逻辑即可，backtrack 核心代码如下：

/* 组合/子集问题回溯算法框架 */
void backtrack(int[] nums, int start) {
    // 回溯算法标准框架
    for (int i = start; i < nums.length; i++) {
        // 做选择
        track.addLast(nums[i]);
        // 注意参数
        backtrack(nums, i);
        // 撤销选择
        track.removeLast();
    }
}


/* 排列问题回溯算法框架 */
void backtrack(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        // 做选择
        track.addLast(nums[i]);
        backtrack(nums);
        // 撤销选择
        track.removeLast();
    }
}

17.电话号码的字母组合

Problem: 17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

提示：

0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。

思路

按题目，按键无重复值，并且是从头往后组合不可复选，可直接上回溯算法。
解题方法

把按钮的值存入数组，然后递归。
Code

class Solution {
    List<String> ans = new ArrayList<>();
    int n;
    String phone;
    public List<String> letterCombinations(String digits) {
        String[] s = new String[]{"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        String track = "";
        n = digits.length();
        if (n == 0) return ans;
        phone = digits;
        // boolean[] used = new boolean[n];
        backtracks(s, track, 0);
        return ans;
    }
    public void backtracks(String[] s, String track, int start){
        if (track.length() == n) {
            ans.add(track);
            return;
        }
        // for(int i = start; i < n; i++) {
            // if(used[i]) continue;
            for(char c: s[phone.charAt(start) - '2'].toCharArray()) {
                track += c;
                // used[i] = true;
                backtracks(s, track, start + 1);
                track = track.substring(0, track.length() - 1);
                // used[i] = false;
            }
        // }
    }
}