Java回溯法解决全排列问题流程详解
短信预约 -IT技能 免费直播动态提醒
题目描述：
给定一不重复的数组，返回其具有的所有全排列（使用 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回溯法 内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
