入门回溯算法，有我这篇就够了

回溯算法几种方法总结

组合

比如从1-9取两个，两两组合有多少种组法，不包括交换位子

例： [1, 3]和[3,1]就是一种组合

77. 组合

题目要求：

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。示例:输入: n = 4, k = 2输出:[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],]

public List<List<Integer>> combine(int n, int k) {
List<Integer> path = new ArrayList<Integer>();
backtracking(n, k, 1, path);
return resList;
}
static List<List<Integer>> resList = new ArrayList<List<Integer>>();
private static void backtracking(int endNumber, int size, int startIndex, List<Integer> path) {
if (path.size() == size) {
resList.add(new ArrayList<Integer>(path));
return;
}
for (int i = startIndex; i <= endNumber; i++) {
path.add(i);
//
backtracking(endNumber, size, i + 1, path);
path.remove(path.size() - 1);
}
}

组合的剪枝

结合上面结合问题看

endNumber（可以表示数组和数的范围） 是所有可取范围

size 表示符合答案条件的长度

startIndex 表示从哪里开始取

path 收集子集，path的大小==size时，里面存的就是符合答案之一;

private static void backtracking(int endNumber, int size, int startIndex, List<Integer> path) {
if (path.size() == size) {
resList.add(new ArrayList<Integer>(path));
return;
}
//要在这里做文章 原先是 i <= endNumber
for (int i = startIndex; i <= endNumber - (size - path.size()) + 1; i++) {
path.add(i);
backtracking(endNumber, size, i + 1, path);
path.remove(path.size() - 1);
}
}

为什么要改成这个呢？

endNumber ={1,2,3,4},size=4时

当path里已经取到{1，2，3，}

分割问题

131. 分割回文串

题目要求：

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例: 输入: “aab” 输出: [ [“aa”,“b”], [“a”,“a”,“b”]

注意事项:

java的中String.substring(startIndex,endIndex)节取的是String从startIndex到(endIndex-1)位子;

如 s = “aab”;

s.substring(0,2)==“aa”;

static public List<List<String>> partition(String s) {
backTracking(s, 0);
return resList;
}
static List<List<String>> resList = new ArrayList<List<String>>();
static List<String> pathList = new ArrayList<String>();
private static void backTracking(String s, int startIndex) {
if (startIndex == s.length()) {
resList.add(new ArrayList<String>(pathList));
return;
}
for (int i = startIndex; i < s.length(); i++) {
if (check(s, startIndex, i + 1)) {
pathList.add(s.substring(startIndex, i + 1));
} else {
continue;
}
backTracking(s, i + 1);
pathList.remove(pathList.size() - 1);
}
}
static private boolean check(String string, int start, int end) {
String s1 = string.substring(start, end);
return s1.equals(new StringBuffer(s1).reverse().toString());
}

子集问题

78. 子集

题目要求：

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例: 输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ];

与组合的不同之处 ：

其实与组合差不多

1.出口不一样，组合找到符合的答案要return回去,而子集不要

static public List<List<Integer>> subsets(int[] nums) {
backTrack(nums, 0);
return resList;
}
static private List<List<Integer>> resList = new ArrayList<List<Integer>>();
static private List<Integer> tmpList = new LinkedList<Integer>();
static private void backTrack(int[] nums, int startIndex) {
//1.出口不一样，只要 收集容器的size<= nums.length就是符合答案之一
if (tmpList.size() <= nums.length) {
resList.add(new LinkedList<Integer>(tmpList));
}
for (int i = startIndex; i < nums.length; i++) {
tmpList.add(nums[i]);
//这里还是往后面取，而不startIndex+1
backTrack(nums, i + 1);
tmpList.remove(tmpList.size() - 1);
}
}

全排列

46全排列

题目要求（数字集中不能有重复）

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

• 输入: [1,2,3]
• 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]

private void dfs(int[] nums, List<Integer> path) {
if (path.size() == nums.length) {
resList.add(new LinkedList<Integer>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (path.contains(nums[i])) {
continue;
}
path.add(nums[i]);
dfs(nums, path);
path.remove(path.size() - 1);
}
}

47全排列 II

题目要求（可以重复）

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

示例 1：

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

方法一（回溯法+交换）

private List<List<Integer>> resList = new ArrayList<List<Integer>>();
private List<Integer> path = new ArrayList<Integer>();
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
dfs(nums, 0);
System.out.println(resList.size());
return resList;
}
private void dfs(int[] nums, int startIndex) {
//交换到最后一位
if (startIndex == nums.length) {
//这里我用了api，将数组转化为list，自己可以重新写个for循环
List<Integer> intList = Arrays.stream(nums).boxed().collect(Collectors.toList());
//如果已经有了这种排法就return
if (resList.contains(intList)) {
return;
}
resList.add(intList);
}
for (int i = startIndex; i < nums.length; i++) {
//当交换到i位子时，如果i-1也是同样的数,i位和startIndex,他们就不用交换了，前提是要
i > startIndex
if (i > startIndex && nums[i] == nums[i - 1]) {
continue;
}
int temp = nums[startIndex];
nums[startIndex] = nums[i];
nums[i] = temp;
dfs(nums, startIndex + 1);
temp = nums[startIndex];
nums[startIndex] = nums[i];
nums[i] = temp;
}
}

方法二（回溯法+收集）

//存放结果
List<List<Integer>> result = new ArrayList<>();
//暂存结果
List<Integer> path = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
//used数组是用来记录基中元素是否用过
boolean[] used = new boolean[nums.length];
Arrays.fill(used, false);
Arrays.sort(nums);
backTrack(nums, used);
return result;
}
private void backTrack(int[] nums, boolean[] used) {
if (path.size()==nums.length) {
result.add(new ArrayList<Integer>(path));
return;
}
//注意这里没有 startIndex,直接从0位子向后取
for (int i = 0; i < nums.length; i++) {
//前面排序了，重复的数肯定挨着，还要确保i-1位是没有过的
if (i>0&&nums[i]==nums[i-1]&&used[i-1]==true) {
continue;
}
//没有用过
if (used[i]==false) {
used[i]= true;//变为用过
path.add(nums[i]);
backTrack(nums, used);
path.remove(path.size()-1);
used[i]=false;//又变为没有用过
}
}
}

两个方法不同：

交换法：

for (int i = startIndex; i < nums.length; i++)//遍历的位子

if (i > startIndex && nums[i] == nums[i - 1]) {continue}//碰到重复的地方

dfs(nums, startIndex + 1);//回溯的地方

收集法：

for (int i = 0; i < nums.length; i++)

if (i>0&&nums[i]==nums[i-1]&&used[i-1]==true) {continue}//用used数组记录元素是否被用过

backTrack(nums, used);

全排列和组合的不同

概念不同

排列 ：组合好子集之后可以交换位子成为另一种排法

组合 ：组合好子集之后可以交换位子，不能成为另一种组合

代码不同（回溯的参数不同）

组合：

for (int i = startIndex; i <= endNumber; i++) {
path.add(i);
//下次开始的子集是 i+1;
backtracking(endNumber, size, i + 1, path);
path.remove(path.size() - 1);
}

全排列：

• 每层都是从0开始搜索而不是startIndex

• 需要used数组记录path里都放了哪些元素了

  //注意这里没有 startIndex,直接从0位子向后取
  for (int i = 0; i < nums.length; i++) {
  //前面排序了，重复的数肯定挨着，还要确保i-1位是没有过的
  if (i>0&&nums[i]==nums[i-1]&&used[i-1]==true) {
  continue;
  }
  //没有用过
  if (used[i]==false) {
  used[i]= true;//变为用过
  path.add(nums[i]);
  backTrack(nums, used);
  path.remove(path.size()-1);
  used[i]=false;//又变为没有用过
  }
  }

最后

以上就是微笑柠檬为你收集整理的入门回溯算法，有我这篇就够了的全部内容，希望文章能够帮你解决入门回溯算法，有我这篇就够了所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。