Java回溯法解决全排列问题流程详解

题目描述：

给定一不重复的数组，返回其具有的所有全排列（使用 List<List > 返回）

思路：

以数组 nums = [1, 2, 3] 为例，其具有的解空间可以用这样一棵树表示，相比看到这里大家就可以知道，这是一道可以用 回溯法 解决的题。

难点：如何保证不选到已经使用过的数组元素 —— 使用 used[] 数组标记该元素是否被使用过

细节请看代码注释

    // 用于存储结果的数组
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    public List<List<Integer>> permute(int[] nums) {
        List<Integer> list = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        backTrack(nums, list, used);
        return ans;
    }
    // 回溯法参数： nums为待排列数组， list存储当前排列结果， used[]标记当前元素是否被使用过
    public void backTrack(int[] nums, List<Integer> list, boolean[] used){
        // 回溯法退出条件，list大小为nums[]长度，即所有元素都已加入排列
        if(list.size() == nums.length){
            // 加入结果数组，注意要 new 新的list (List为按指针所指地址存储，不然每次加的都是同一个)
            ans.add(new ArrayList(list));
            return;
        }
        // 循环以每个元素开始排列
        for(int i=0; i<nums.length; i++){
            // 元素未被使用过加入排列
            if(!used[i]){
                // 在排列中加入当前元素，并将used[i]修改为true
                list.add(nums[i]);
                used[i] = true;
                // 递归调用 backTrack
                backTrack(nums, list, used);
                // 回溯，去掉当前元素，并将used置为false
                list.remove(list.size() - 1);
                used[i] = false;
            }
        }
    }

变式一

题目描述：给定一具有重复数字的序列， 返回所有不重复的全排列

示例：

这道题是全排列的变式题， 只需要对全排列写法加入对重复情况去除的判断即可，于是本题的重心转移到了如何判断是否会产生重复序列。

我们可以思考什么情况会产生重复序列， 我们先对 nums[] 按从小到大排序， 限制每次填入的数字都是重复数字的从左到右的第一个数字

class Solution {
    Boolean[] visit;
    List<List<Integer>> ans;
    public List<List<Integer>> permuteUnique(int[] nums) {
        visit = new Boolean[nums.length];
        Arrays.fill(visit, false);
        List<Integer> list = new ArrayList<>();
        ans = new ArrayList<>();
        Arrays.sort(nums);
        backTrack(nums, list);
        return ans;
    }
    public void backTrack(int[] nums, List<Integer> list){
        if(nums.length == list.size()){
            ans.add(new ArrayList(list));
            return;
        }
        for(int i=0; i<nums.length; i++){
            // 当前元素用过 + 限制每轮填入的字符都是重复字符的从左到右的第一个字符
            if(visit[i] || (i > 0 && !visit[i-1] && nums[i] == nums[i-1])){
                continue;
             }
            list.add(nums[i]);
            visit[i] = true;
            backTrack(nums, list);
            visit[i] = false;
            list.remove(list.size() - 1);
        }
    }
}

变式：字符排序

class Solution {
    List<String> ans = new ArrayList<>();
    public String[] permutation(String s) {
        // 思路： 回溯法典型例题 —— 含重复问题
        char[] array = s.toCharArray();
        Arrays.sort(array);
        Boolean[] used = new Boolean[array.length];
        Arrays.fill(used, false);
        backTack(array, used, new StringBuilder());
        String[] res = new String[ans.size()];
        for(int i=0; i<ans.size(); i++){
            res[i] = ans.get(i);
        }
        return res;
    }
    public void backTack(char[] array, Boolean[] used, StringBuilder sb){
        if(array.length == sb.length()){
            ans.add(new String(sb));
        }
        for(int i=0; i<array.length; i++){
           if(used[i]){
               continue;
           }
           if(i>0 && array[i]==array[i-1] && !used[i-1]){
               continue;
           }
            sb.append(array[i]);
            used[i] = true;
            backTack(array, used, sb);
            sb.deleteCharAt(sb.length() - 1);
            used[i] = false;
        }
    }
}

到此这篇关于Java回溯法解决全排列问题流程详解的文章就介绍到这了,更多相关Java回溯法 内容请搜索自由互联以前的文章或继续浏览下面的相关文章希望大家以后多多支持自由互联！