今天要做的几道题不是随机的，是我事先留下来的四道题。组合总和，组合总和2，全排列，全排列2这种题型其实是有共同点的，一方面可以是动规解决。另一方面就是典型的回溯算法。
其实关于回溯我本来有打算专门写一篇自己整理的笔记，但是真到了落笔又无从写起。因为他的意义很明确。
回溯算法
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
然后继续说单纯从文字来说是没意义的，理解谁都能理解，但是真正到了问题上要怎么去想才是问题所在。我之前为了统一做这几道题啃了大量的回溯知识，但是真正到了实践中开始四处碰壁，说实话就是第一题组合总和就林林总总提交了不下十次，微调微调微调，还有思路调整什么的，反正如果有机会还是打算专门整理一篇回溯的学习笔记，现在开始做题吧。
组合总和
题目：给定一个无重复元素的数组 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]
]
思路:这道题其实虽说是标准的回溯题，但是一些常识性的技巧还是和回溯无关的，一点点分析。
- 这道题说了target和数组中元素都是正整数，如果单元素值大于target的可以直接pass。
- 解集不能包含重复的集合。所以A,B,C如果可以，在判断完A后，从B开始判断，就不能再操作B之前的元素例如A了。也就是每次判断的target减去当前值下一轮不能算当前值前面的元素。
- 这道题还说了每个元素可以无数次使用，所以每次target减去当前值的下一轮循环还是要从当前值开始。
- 说一下我上文提到了打算用减法来实现这个题。所以target减去当前值，然后不断的回溯判断。这个减去当前值只有三种可能：
- 结果大于0，则可以继续往下判断。
- 结果等于0，说明当前的解集正好是对的，所以将这个集添加到结果集。
- 结果小于0，基于上面说的都是正整数，小于0明显这条分支不对了，则直接放弃。
以上的思路是我一点点写的，可能顺序不对，但是将整体代码逻辑大概列出来了，接下来我直接贴代码:
class Solution {
List<List<Integer>> res;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
if(candidates.length==0) return res;
res = new ArrayList<List<Integer>>();
dfs(0,candidates,target,new ArrayList<Integer>());
return res;
}
public void dfs(int start,int[] candidates,int target,List<Integer> list){
if(target<0) return;
if(target==0){
res.add(new ArrayList<Integer>(list));
}else{
for(int i = start;i<candidates.length;i++){
if(candidates[i]<=target){
list.add(candidates[i]);
dfs(i,candidates,target-candidates[i],list);
list.remove(list.size()-1);
}
}
}
}
}
我代码中没写什么逻辑，因为我亲自经受了一段代码四分之三都是注释，看起来不舒服还复杂，这里单独就这个代码写点注释：
首先这个集合是空则直接返回空集，这个没啥说的。
确定不是空集了开始进行回溯判断。
这个方法有四个参数：
- 当前元素的下标。
- 这个数组（有的答案上排序了，但是我觉得没啥必要，所以这里就是原生数组，没排序）
- target（这个是被处理过的元素，虽然名字是target，但是是每次被减过剩余的值。）
- 当前集合的元素。
然后方法里是首先三个判断，等于target直接返回。小于target也是返回。只有大于target才会继续往下遍历数组。因为不能重复而且一个元素可以复用，所以这里是从start开始遍历，后面的元素小于等于target才有必要继续遍历，不然肯定不符合。
最后的list.remove(list.size()-1)是每次把最后一个元素删除，不管真假，这个就是回溯的主要思路：回溯到没走这步的过程。
组合总和2
题目：给定一个数组 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]
]
思路：这道题其实就是上面题的简单的变化。而且我上题中已经提到了，因为可重复使用所以下次遍历从当前值开始遍历，这个题说的是不可重复使用，那么从当前元素的下一个开始遍历就行了。我去简单是写下代码。
好的吧，我都写完代码了才发现这个题除了不能重复用还有给定的数组不是唯一的，还得判一个重，，，我去再多做一步。这个判重有两种做法，一种是set变成不重复的数组，然后再转成数组，用这个数组做字典，另一种就是这个数组排序，然后如果第二个元素等于第一个元素，直接continue。因为还没尝试所以不知道哪个性能好，但是我打算用第一种，起码代码的逻辑不用变。
很好，用了第一种方式，结果发现还是不行，因为这个重复元素，是一个元素不能重复用， 但是比如上面示例这个1，1是可以都用的，这么看只能用第二种方式了。排序，然后第二个元素如果和前面的元素一样直接continue。
用了第二种方法做是做出来了，但是性能没我想的好，。。
额，没事了，一样的代码又提交了一边，立刻从5ms到3ms，从排名六十多到排名百分之九十八了。
我直接贴代码:
class Solution {
List<List<Integer>> res;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
if(candidates.length==0) return res;
res = new ArrayList<List<Integer>>();
Arrays.sort(candidates);
dfs(0,candidates,target,new ArrayList<Integer>());
return res;
}
public void dfs(int start,int[] array,int target, List<Integer> list){
if(target<0) return;
if(target==0){
res.add(new ArrayList<Integer>(list));
}else{
for(int i = start;i<array.length;i++){
if(i>start && array[i]==array[i-1]) continue;
if(target>=array[i]){
list.add(array[i]);
dfs(i+1,array,target-array[i],list);
list.remove(list.size()-1);
}
}
}
}
}
其实这道题重点是理解上一道题，就很容易做出来。至于判重也不是只有这一种方法，不过我就不多想了，直接下一题了。
全排列
题目：给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
思路:这道题怎么说呢，就是笛卡尔积的结果。数多了肯定贼复杂。这里用回溯再好不过了，总好过一个个情况写吧。然后其实逻辑也是挺清楚的，难点就是要知道某个元素是否已经被使用了。这个其实我目前有两个想法。一种是用一个辅助数组，0，1来表示使用情况。另一中是用set。因为set可以用contains来判断这个元素是否存在。我先去理理思路然后撸代码。
在做的过程中因为要用到回溯的返回上一步，我不清楚这个set怎么删除上一个放进去的元素，所以这里用了LinkedList。我直接贴代码：
class Solution {
List<List<Integer>> res;
public List<List<Integer>> permute(int[] nums) {
res = new ArrayList<List<Integer>>();
LinkedList<Integer> temp = new LinkedList<Integer>();
dfs(nums,temp);
return res;
}
public void dfs(int[] nums,LinkedList<Integer> temp){
if(temp.size()==nums.length) {
res.add(new ArrayList<Integer>(temp));
return;
}
for(int i : nums){
if(temp.contains(i)) continue;
temp.add(i);
dfs(nums,temp);
temp.removeLast();
}
}
}
如上代码，就是一个很经典的回溯。如果是用到的元素则直接continue。不然的话添加，递归，回溯。其实这个和树的遍历有点像。如果不懂的话就品，细品。
我看了性能排行第一的代码，就是一样的套路，只不过是我这里用的LinkedList在原数组的基础上判断是否使用过某元素。而人家用了一个辅助数组，这样性能不用来回来去contains判断，性能好很多。我直接贴出来吧，其实只要能看懂我的代码这个也只不过是一点微调而已。
class Solution {
List<List<Integer>> res = new LinkedList<>();
public List<List<Integer>> permute(int[] nums) {
backtrack(nums, new boolean[nums.length], new LinkedList<>());
return res;
}
public void backtrack(int[] nums, boolean[] visited, LinkedList<Integer> track) {
if (track.size() == nums.length) {
res.add(new LinkedList<>(track));
return;
}
for (int i = 0; i < nums.length; i++) {
if (visited[i]) {
continue;
}
visited[i] = true;
track.add(nums[i]);
backtrack(nums, visited, track);
track.removeLast();
visited[i] = false;
}
}
}
好了，这道题就这样，下一题。
全排列2
题目:给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
思路：这个题其实和上一个差不多。如果用我的方式直接在原LinkedList上判断是否用过此元素确实要改动思路。但是用辅助数组的方式容易做多了。具体的思路可以参考上面的组合总和2，就是先排序，然后判重。我去写代码了。
好了，我直接贴代码：
class Solution {
List<List<Integer>> res;
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
res = new ArrayList<List<Integer>>();
List<Integer> list = new ArrayList<Integer>();
boolean[] flag = new boolean[nums.length];
dfs(nums,flag,list);
return res;
}
public void dfs(int[] nums,boolean[] flag, List<Integer> list){
if(list.size()==nums.length){
res.add(new ArrayList<Integer>(list));
return;
}
for(int i = 0;i<nums.length;i++){
if(flag[i]) continue;
if(i>0 && nums[i]==nums[i-1] && flag[i-1]) continue;
flag[i] = true;
list.add(nums[i]);
dfs(nums,flag,list);
list.remove(list.size()-1);
flag[i] = false;
}
}
}
其实这个题和上一道除了中间多了个判断剩下是一样的。因为之前排过序了，所以可能确定相同的数肯定是挨着的。只要后面的元素等于前面的元素就说明是重复元素，排列的组合和前面那个是一样的。这个逻辑很简单，如果是重复元素，并且前面元素的排列组合已经排列完了（因为前面那个已经是true了）这个直接跳过就行了。
然后这四道回溯经典题目就到这里了，正常来讲应该这里还有一个N皇后不可避免。但是因为我是按照顺序刷的题，所以N皇后还没刷到，所以这里还是先不说了，反正刷到以后还是会写心得的。
另外通过刷这几道题和看资料，我也是打算把回溯这块的东西整理整理专门写成一篇笔记的。
这篇文章就到这里，如果稍微帮到你了记得点个喜欢点个关注，也祝大家新年快乐！目前疫情比较严重，也祝大家生活愉快，放宽心态。
