46. 全排列、77. 组合、784. 字母大小写全排列

今天的三道题都是用的回溯的算法，参考这里，还有这里

46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    List<List<Integer>> res = new LinkedList<>();

    public List<List<Integer>> permute(int[] nums) {
        LinkedList<Integer> track = new LinkedList<>();
        // 回溯算法
        backTrack(nums, track);

        return res;
    }

    public void backTrack(int[] nums, LinkedList<Integer> track) {
        // 满足条件
        if (track.size() == nums.length) {
            res.add(new ArrayList<>(track));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            // 排除已经存在的数字
            if (track.contains(nums[i])) continue;
            // 做选择
            track.add(nums[i]);
            // 进入下一层
            backTrack(nums, track);
            // 取消选择，即回溯，回到上一层
            track.removeLast();
        }
    }
}

结果如下：

77. 组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combinations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    List<List<Integer>> res = new LinkedList<>();

    public List<List<Integer>> combine(int n, int k) {
        LinkedList<Integer> track = new LinkedList<>();
        // 回溯算法
        backTrack(n, k, 1, track);
        
        return res;
    }

    public void backTrack(int n, int k, int start, LinkedList<Integer> track) {
        // 满足条件
        if (track.size() == k) {
            res.add(new ArrayList<>(track));
            return;
        }

        for (int i = start; i <= n; i++) {
            // 做选择
            track.add(i);
            // 进入下一层
            backTrack(n, k, i + 1, track);
            // 取消选择，即回溯
            track.removeLast();
        }
    }
}

结果如下：

784. 字母大小写全排列

给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。

示例：

输入：S = "a1b2"
输出：["a1b2", "a1B2", "A1b2", "A1B2"]

输入：S = "3z4"
输出：["3z4", "3Z4"]

输入：S = "12345"
输出：["12345"]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/letter-case-permutation
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    List<String> res = new LinkedList<>();

    public List<String> letterCasePermutation(String s) {
        StringBuilder track = new StringBuilder();
        // 回溯算法
        backTrack(s, 0, track);

        return res;
    }

    public void backTrack(String s, int start, StringBuilder track) {
        // 判断满足条件
        if (track.length() == s.length()) {
            res.add(track.toString());
            return;
        }

        for (int i = start; i < s.length(); i++){
            // 数字直接加然后回溯
            if (Character.isDigit(s.charAt(i))){
                // 做选择
                track.append(s.charAt(i));
                // 下一层决策树
                backTrack(s, i + 1, track);
                // 回溯
                track.deleteCharAt(track.length() - 1);
            } else {
                char upper = Character.toUpperCase(s.charAt(i));
                track.append(upper);
                backTrack(s, i + 1, track);
                track.deleteCharAt(track.length() - 1);

                char lower = Character.toLowerCase(s.charAt(i));
                track.append((lower));
                backTrack(s, i + 1, track);
                track.deleteCharAt(track.length() - 1);
            }
        }
    }
}

结果如下：