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回溯法 内容请搜索编程宝库以前的文章，希望以后支持编程宝库！

 一、简介概念：事务是数据库操作的最小工作单元，是作为单个逻辑工作单元执行的一系列操作，这些操作一起提交，要么都执行，要么都不执行。事务时一组不可分割的操作集合（工作逻辑单元）。简而言之，就是一系列 ...