算法日记 20-22 day 回溯算法

补这两天的博客，看看这两天的题目吧。

题目：组合总和

39. 组合总和 - 力扣（LeetCode）

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

题目分析：

组合问题，那么就可以考虑回溯的解法。题目中需要注意的是无重复元素，并且数字可以重复取。和之前的题一样，将题目抽象为树形结构看看。

然后就是递归五部曲。

public class Solution {IList<IList<int>> res=new List<IList<int>>();IList<int> path=new List<int>();public IList<IList<int>> CombinationSum(int[] candidates, int target) {BackTracking(candidates,target,0);return res;}public void BackTracking(int[] candidates,int target,int index){if(target<0) return;if(target==0){res.Add(new List<int>(path));return ;}for(int i=index;i<candidates.Length;i++){target-=candidates[i];path.Add(candidates[i]);BackTracking(candidates,target,i);//注意可以重复取值，所以传itarget+=candidates[i];path.RemoveAt(path.Count-1);}}
}

题目：组合总和 2

40. 组合总和 II - 力扣（LeetCode）

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

注意：解集不能包含重复的组合

题目分析：

和上一题的差别在于每个数字只能用一次，而且数字可能有重复，并且不能有重复组合。

那怎么去进行去重。题目要求数子只能用一次，这里其实可以使用一个索引或者一个标志数组来判断。

先看看树形结构

图中就是使用了used的标志数组来进行去重，代码中我没有使用这种方式，不过能表示的意思是一样的。

对于used数组的使用，我们接下来用的会更加频繁。

public class Solution {IList<IList<int>> res=new List<IList<int>>();IList<int> path=new List<int>();public IList<IList<int>> CombinationSum2(int[] candidates, int target) {Array.Sort(candidates);BackTracking(candidates,target,0);return res;}public void BackTracking(int[] candidates,int target,int startIndex){if(target<0) return;if(target==0){res.Add(new List<int>(path));return;}for(int i=startIndex;i<candidates.Length;i++){if(i>startIndex&&candidates[i]==candidates[i-1]) continue;target-=candidates[i];path.Add(candidates[i]);BackTracking(candidates,target,i+1);//注意这里传的是i+1而不是StartIndex,这样可以跳过重复的值target+=candidates[i];path.RemoveAt(path.Count-1);}}
}

题目：分割回文串

131. 分割回文串 - 力扣（LeetCode）

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串。返回 s 所有可能的分割方案。

题目分析：

这一题无非就是两个问题，字符组合以及回文判断。

例如对于字符串abcdef：

组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中再选取第三个.....。
切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段.....。

这么看来，其实也能形成一个树形结构。

那代码还是和其他回溯问题差不多，只是多了回文判断。

public class Solution {IList<IList<string>> res=new List<IList<string>>();IList<string> path=new List<string>();public IList<IList<string>> Partition(string s) {BackTracking(s,0);return res;}public void BackTracking(string s,int startIndex){if(startIndex>=s.Length){res.Add(new List<string>(path));return ;}for(int i=startIndex;i<s.Length;i++){if(isHuiWen(s,startIndex,i)){//回文判断path.Add(s.Substring(startIndex,i-startIndex+1));//切割字串}else continue;BackTracking(s,i+1);path.RemoveAt(path.Count-1);}}public bool isHuiWen(string str,int start,int end){for(int i=start,j=end;i<j;i++,j--){if(str[i]!=str[j]) return false;}return true;}
}

题目：复原IP地址

93. 复原 IP 地址 - 力扣（LeetCode）

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你不能重新排序或删除 s 中的任何数字。你可以按任何顺序返回答案。

题目分析：

和上一题差不多的道理，看看树形

代码如下：

public class Solution {IList<string> res=new List<string>();public IList<string> RestoreIpAddresses(string s) {if (s.Length < 4 || s.Length > 12) return res;BackTracking(s,0,0);return res;}public void BackTracking(string s,int start,int pointNum){if(pointNum==3){// 判断第四段子字符串是否合法，如果合法就放进result中if(isIP(s,start,s.Length-1)){res.Add(s);}return;}for(int i=start;i<s.Length;i++){if(isIP(s,start,i)){s=s.Insert(i+1,".");BackTracking(s,i+2,pointNum+1);//加入了.，所以加2s=s.Remove(i+1,1);}else break;}}public bool isIP(string s,int start,int end){if (start > end) return false;if (s[start] == '0' && start != end) return false;int num = 0;for (int i = start; i <= end; i++){if (s[i] > '9' || s[i] < '0') return false;num = num * 10 + s[i] - '0';if (num > 255) return false;}return true;}
}

题目：子集

78. 子集 - 力扣（LeetCode）

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的

子集（幂集）。解集不能包含重复的子集。你可以按 任意顺序 返回解集。

题目分析：

还是和组合问题一个套路，不过需要注意的是，空集是任何集合的子集。

public class Solution {IList<IList<int>> res=new List<IList<int>>();IList<int> path=new List<int>();public IList<IList<int>> Subsets(int[] nums) {BackTracking(nums,0);return res;}public void BackTracking(int[] nums,int start){res.Add(new List<int>(path));//放在开头，注意空集也是子集if(start>=nums.Length) return;for(int i=start;i<nums.Length;i++){path.Add(nums[i]);BackTracking(nums,i+1);path.RemoveAt(path.Count-1);}}
}

题目：子集 2

90. 子集 II - 力扣（LeetCode）

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的

子集(幂集）。解集不能包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

题目分析：

和上一题一样的，不过数组中可能会出现重复元素，不过是子集，我们只需要判断相邻两个值即可。

public class Solution {IList<IList<int>> res=new List<IList<int>>();IList<int> path=new List<int>();public IList<IList<int>> SubsetsWithDup(int[] nums) {Array.Sort(nums);BackTracking(nums,0);return res;}public void BackTracking(int[] nums,int start){res.Add(new List<int>(path));if(start>=nums.Length) return;for(int i=start;i<nums.Length;i++){if(i>start&&nums[i]==nums[i-1]) continue;path.Add(nums[i]);BackTracking(nums,i+1);path.RemoveAt(path.Count-1);}}
}

题目：递增子序列

491. 非递减子序列 - 力扣（LeetCode）

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

题目分析：

序列需要递增，并且大于等于2，并且数组中有重复。怎么去重？

可以看到，我们实际上去重的部分是树层。这里我们可以使用hash来记录使用过的数字。

public class Solution {IList<IList<int>> res=new List<IList<int>>();IList<int> path=new List<int>();public IList<IList<int>> FindSubsequences(int[] nums) {BackTracking(nums,0);return res;}public void BackTracking(int[] nums,int start){if(path.Count>=2){res.Add(new List<int>(path));}//树层去重HashSet<int> temp=new HashSet<int>();//记录每一层已经使用的数for(int i=start;i<nums.Length;i++){if(path.Count>0&&nums[i]<path[path.Count-1]||temp.Contains(nums[i])) continue;temp.Add(nums[i]);path.Add(nums[i]);BackTracking(nums,i+1);path.RemoveAt(path.Count-1);}}
}

题目：全排列

46. 全排列 - 力扣（LeetCode）

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

题目分析：

画出树形图来看

实际上我们需要考虑的是树枝上的去重，这里就用到了之前的used数组来进行标记。

public class Solution {IList<IList<int>> res=new List<IList<int>>();IList<int> path=new List<int>();public IList<IList<int>> Permute(int[] nums) {bool[] used=new bool[nums.Length];//记录一层中，那些数被使用过BackTracking(nums,used);return res;}public void BackTracking(int[] nums,bool[] used){if(path.Count==nums.Length){res.Add(new List<int>(path));return;}for(int i=0;i<nums.Length;i++){//每次都从0开始，这样就能重复获取if(used[i])continue;//当前值被使用了，跳过used[i]=true;path.Add(nums[i]);BackTracking(nums,used);path.RemoveAt(path.Count-1);used[i]=false;}}
}

题目：全排列 2

47. 全排列 II - 力扣（LeetCode）

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

题目分析：

比上一题多了一个重复。

根据树形结构来看，我们还需要对树层进行去重。

public class Solution {IList<IList<int>> res=new List<IList<int>>();IList<int> path=new List<int>();public IList<IList<int>> PermuteUnique(int[] nums) {Array.Sort(nums);bool[] used=new bool[nums.Length];BackTracking(nums,used);return res;}public void BackTracking(int[] nums,bool[] used){if(path.Count==nums.Length){res.Add(new List<int>(path));return;}for(int i=0;i<nums.Length;i++){if(i>0&&nums[i]==nums[i-1]&&!used[i-1]) continue;//树层去重，userd[i-1]==false保证是同一层if(used[i]) continue;used[i]=true;path.Add(nums[i]);BackTracking(nums,used);used[i]=false;path.RemoveAt(path.Count-1);}}
}

对于更详细的解析与其他语言的代码块，可以去代码随想录上查看。

代码随想录 (programmercarl.com)