此为回溯算法刷题的一些代码，希望能给读者以启发；
刷题目录：
开始前，搬运大佬的解题思路：
解决一个回溯问题，实际上就是一个决策树的遍历过程。你只需要思考 3 个问题：
1、路径：也就是已经做出的选择。
2、选择列表：也就是你当前可以做的选择。
3、结束条件：也就是到达决策树底层，无法再做选择的条件。
如果你不理解这三个词语的解释，没关系，我们后面会用「全排列」和「N 皇后问题」这两个经典的回溯算法问题来帮你理解这些词语是什么意思，现在你先留着印象。
代码方面，回溯算法的框架：
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
比如在对数字进行全排列过程中，大家都就会采用回溯法的思想，将其以树的形式表示出来大概就是这样。
从根节点开始，待选[1,2,3]已选[ ]。选择3，则待选为[1，2] 已选[3]，往下选择1，待选为[2]已选[1,3],向下只有一个选择，后续不表。然后回退，仅一个已选项，继续回退至待选为[1，2] 已选[3]，1已经选过则选2...2支路选择结束回退至根节点重新选择，循环往复。
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入:[1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
算法一：
public class Solution {
public List<List<Integer>> permute(int[] nums) {
int len = nums.length;
List<List<Integer>> res = new ArrayList<>();
if (len == 0) {
return res;
}
// 使用哈希表检测一个数字是否使用过
//Set<Integer> used = new HashSet<>(len);
Deque<Integer> path = new ArrayDeque<>(len);
dfs(nums, len, 0, path, res);
return res;
}
算法二：(大同小异)
private void dfs(int[] nums, int len, int depth,
Deque<Integer> path,
List<List<Integer>> res) {
if (depth == len) {
res.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < len; i++) {
if (!path.contains(nums[i])) {
//used.add(i);
path.addLast(nums[i]);
dfs(nums, len, depth + 1, path, res);
path.removeLast();
//used.remove(i);
}
}
}
}
难度中等
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入:[1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
class Solution {
List<List<Integer>> res = new LinkedList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
LinkedList<Integer> track=new LinkedList<Integer>();
int[] used=new int[nums.length];
backtrack(nums,track,used);
return res;
}
public void backtrack(int[] nums,LinkedList<Integer> track,int[] used)
{
if(nums.length==track.size())
{
if(!res.contains(track)) res.add(new LinkedList(track));
return ;
}
for(int i=0;i<nums.length;i++)
{
if(used[i]==1)
{
continue;
}
track.add(nums[i]);
used[i]=1;
backtrack(nums, track,used);
// 取消选择
track.removeLast();
used[i]=0;
}
}
}
难度中等
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入:nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
backtrack(0, nums, res, new ArrayList<Integer>());
return res;
}
private void backtrack(int i, int[] nums, List<List<Integer>> res, ArrayList<Integer> tmp) {
res.add(new ArrayList<>(tmp));
for (int j = i; j < nums.length; j++) {
tmp.add(nums[j]);
backtrack(j + 1, nums, res, tmp);
tmp.remove(tmp.size() - 1);
}
}
}
难度中等
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入:[1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
backtrack(0, nums, res, new ArrayList<Integer>());
return res;
}
private void backtrack(int i, int[] nums, List<List<Integer>> res, ArrayList<Integer> tmp) {
res.add(new ArrayList<>(tmp));
for (int j = i; j < nums.length; j++) {
if(j>i&&nums[j]==nums[j-1]) continue;
tmp.add(nums[j]);
backtrack(j + 1, nums, res, tmp);
tmp.remove(tmp.size() - 1);
}
}
}
难度中等
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1:
输入:candidates =[2,3,6,7],target =7,
所求解集为:
[
[7],
[2,2,3]
]
示例 2:
输入:candidates = [2,3,5],target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
class Solution {
List<List<Integer>> res=new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
LinkedList<Integer> track = new LinkedList<>();
if(candidates.length==0) return null;
backtrace(0,candidates,target,track);
return res;
}
public void backtrace(int start,int[] candidates,int target,LinkedList<Integer> track)
{
if(sum(track)==target)res.add(new LinkedList(track));
for(int i=start;i<candidates.length;i++)
{
if(sum(track)>target)continue;
track.add(candidates[i]);
backtrace(i,candidates,target,track);
track.removeLast();
}
}
public int sum(LinkedList<Integer> track)
{
int Sum=0;
for(int item:track) Sum+=item;
//System.out.println(Sum);
return Sum;
}
}
难度中等
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。
示例 1:
输入:candidates =[10,1,2,7,6,1,5], target =8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
示例 2:
输入:candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]
class Solution {
List<List<Integer>> res=new ArrayList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
LinkedList<Integer> track = new LinkedList<>();
if(candidates.length==0) return null;
Arrays.sort(candidates);
backtrace(0,candidates,target,track);
return res;
}
public void backtrace(int start,int[] candidates,int target,LinkedList<Integer> track)
{
if(target<0)return ;
if(target==0)res.add(new LinkedList(track));
for(int i=start;i<candidates.length;i++)
{
//if(track.contains(candidates[i]))continue;
if(i>start&&candidates[i]==candidates[i-1])continue;
track.add(candidates[i]);
target-=candidates[i];
backtrace(i+1,candidates,target,track);
track.removeLast();
target+=candidates[i];
}
}
}
难度中等
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
所有数字都是正整数。
解集不能包含重复的组合。
示例 1:
输入:k= 3,n= 7
输出:[[1,2,4]]
示例 2:
输入:k= 3,n= 9
输出:[[1,2,6], [1,3,5], [2,3,4]]
class Solution {
List<List<Integer>> res=new ArrayList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
if(k==0||k>45)return res;
LinkedList<Integer> track = new LinkedList<>();
backtrace(1,track,n,k);
return res;
}
public void backtrace(int loc,LinkedList<Integer> track,int target,int k)
{
if(target<0)return;
else if(track.size()==k&&target==0) res.add(new ArrayList<>(track));
for(int i=loc;i<10;i++)
{
track.add(i);
target-=i;
backtrace(i+1,track,target,k);
target+=i;
track.removeLast();
}
}
}
难度中等
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例:
输入:"aab"
输出:
[
["aa","b"],
["a","a","b"]
]
class Solution {
List<List<String>> res=new ArrayList<>();
public List<List<String>> partition(String s) {
LinkedList<String> track=new LinkedList<>();
int len=s.length();
if(len<1) return res;
backtrace(s,track,len,0);
return res;
}
public void backtrace(String s,LinkedList<String> track,int len,int start)
{
if(len==start)res.add(new LinkedList(track));
for(int i=start;i<len;i++)
{
if(!check(s,start,i))continue;
track.add(s.substring(start,i+1));
backtrace(s,track,len,i+1);
track.removeLast();
}
}
public boolean check(String s,int left,int right)
{
while(left<right)
{
if(s.charAt(left)==s.charAt(right))
{
left++;
right--;
}
else return false;
}
return true;
}
}
