回溯算法实战系列之全排列问题-一一网

这是我参与更文挑战的第28天，活动详情查看：更文挑战

这两天在研究回溯算法，组合问题，求全排列，求子集等这几类问题都是回溯算法运用的经典问题。

这篇文章我主要挑选出两道求解全排列的问题，难度都是中级，来介绍回溯算法的应用思想。

题目实例Ⅰ

784. 字母大小写全排列

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

示例 1：

输入：S = “a1b2”

输出：[“a1b2”, “a1B2”, “A1b2”, “A1B2”]

示例 2：

输入：S = “3z4”

输出：[“3z4”, “3Z4”]

示例 3：

输入：S = “12345”

输出：[“12345”]

提示：

S 的长度不超过12。
S 仅由数字和字母组成。

友情链接：leetcode-cn.com/problems/le…

代码实战Ⅰ

class Solution {
    StringBuilder path = new StringBuilder();
    public List<String> letterCasePermutation(String s) {
        ArrayList<String> res = new ArrayList<>();
        backTracking(s, res, 0);
        return res;
    }

    public void backTracking(String s, ArrayList<String> res, int index) {
        if (path.length() == s.length()) {
            res.add(new String(path.toString()));
            return;
        }

        for (int i = index; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (Character.isDigit(ch)) {
                path.append(ch);
                backTracking(s, res, i + 1);
                path.deleteCharAt(path.length() - 1);
            } else {
                path.append(Character.toLowerCase(ch));
                backTracking(s, res, i + 1);
                path.deleteCharAt(path.length() - 1);

                path.append(Character.toUpperCase(ch));
                backTracking(s, res, i + 1);
                path.deleteCharAt(path.length() - 1);
            }
        }
    }
}

复制代码

题目实例Ⅱ

47. 全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序返回所有不重复的全排列。

示例 1：

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

输出：

[[1,1,2],

[1,2,1],

[2,1,1]]

示例 2：

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

输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

1 <= nums.length <= 8
-10 <= nums[i] <= 10

友情链接：leetcode-cn.com/problems/pe…

代码实战Ⅱ

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
        int depth = 0;
        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        backTracking(nums, used, path, depth, res);
        return res;
    }

    public static void backTracking(int[] nums, boolean[] used, LinkedList<Integer> path, int depth, List<List<Integer>> res) {
        if (nums.length == depth) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                    continue;
                }
                path.add(nums[i]);
                used[i] = true;
                backTracking(nums, used, path, depth + 1, res);
                used[i] = false;
                path.removeLast();
            }
        }
    }
}
复制代码