补这两天的博客，看看这两天的题目吧。
题目：组合总和
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);//注意可以重复取值，所以传i
target+=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);//加入了.，所以加2
s=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)