目录
1.格雷编码
2. 复原 IP 地址
3. 火柴拼正方形
1.格雷编码
n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：
- 每个整数都在范围
[0, 2n - 1]内（含0和2n - 1） - 第一个整数是
0 - 一个整数在序列中出现 不超过一次
- 每对 相邻 整数的二进制表示 恰好一位不同 ，且
- 第一个 和 最后一个 整数的二进制表示 恰好一位不同
给你一个整数 n ，返回任一有效的 n 位格雷码序列 。
示例 1：
输入：n = 2 输出：[0,1,3,2] 解释： [0,1,3,2] 的二进制表示是 [00,01,11,10] 。 - 00 和 01 有一位不同 - 01 和 11 有一位不同 - 11 和 10 有一位不同 - 10 和 00 有一位不同 [0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。 - 00 和 10 有一位不同 - 10 和 11 有一位不同 - 11 和 01 有一位不同 - 01 和 00 有一位不同
示例 2：
输入：n = 1 输出：[0,1]
提示：
1 <= n <= 16
分析：感觉从题解来看，这个题好像和回溯没什么很大的关系 力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
#include <bits/stdc++.h>
using namespace std;
main()
{
int n,i,j,head=1;
cin>>n;
vector<int> res;
res.push_back(0);
cout<<0<<" ";
for(i=0;i<n;i++)
{
for(j=res.size()-1;j>=0;j--)
{
res.push_back(head+res[j]);
cout<<head+res[j]<<" ";
}
head<<=1;
}
}
2. 复原 IP 地址
有效 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 中的任何数字。你可以按 任何 顺序返回答案。
示例 1：
输入：s = "25525511135" 输出：["255.255.11.135","255.255.111.35"]
示例 2：
输入：s = "0000" 输出：["0.0.0.0"]
示例 3：
输入：s = "101023" 输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
提示：
1 <= s.length <= 20s仅由数字组成
分析：这个就是要分割字符串了，刚开始只觉得和回文串是一样的，所以一直在想着一个字符一个字符去判断，结果到后面判断不清楚了，去看了别人的题解才想到完全可以直接用255来判断..
#include <bits/stdc++.h>
using namespace std;
bool isvaild(string s,int start,int end)
{
if(start > end) return false;
if(s[start]=='0' && start !=end) return false;
int i,num=0;
for(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;
}
void f(string s,int index,int point)
{
int i;
if(point==3)
{
if(isvaild(s,index,s.size()-1))
{
cout<<s<<endl;
return;
}
}
for(i=index;i<s.size();i++)
{
if(isvaild(s,index,i))
{
s.insert(s.begin()+i+1,'.');
point++;
f(s,i+2,point);
point--;
s.erase(s.begin()+i+1);
}
else break;
}
}
main()
{
string s;
cin>>s;
if(s.size()<4 || s.size()>12) return 0;
f(s,0,0);
}
3.火柴拼正方形
你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。
如果你能使这个正方形，则返回 true ，否则返回 false 。
示例 1:
输入: matchsticks = [1,1,2,2,2] 输出: true 解释: 能拼成一个边长为2的正方形，每边两根火柴。
示例 2:
输入: matchsticks = [3,3,3,3,4] 输出: false 解释: 不能用所有火柴拼成一个正方形。
提示:
1 <= matchsticks.length <= 151 <= matchsticks[i] <= 108
分析：之前有一道题用了排序，就让我想到了可以先排序，然后算一下总和，通过总和是不是4的倍数和总和/4是不是大于最大值来剪枝，之后就是要用到回溯，在回溯中，如果加和大于总和/4的话就要剪枝，这样可以减少计算量，然后剩下的就是回溯了，我本来想的是用一个字符串s1来记录然后放到4个result中，但是它直接就是result[4]，然后从这四个类似于堆的vector下手去做，就简单了好多，感觉真的非常的聪明欸
#include <bits/stdc++.h>
using namespace std;
int num[21],sum=0,n;
vector<int> result(4);
bool f(int index)
{
int i;
if(index==n) return true;
for(i=0;i<4;i++)
{
result[i]+=num[index];
if(result[i]<=sum && f(index+1))
return true;
result[i]-=num[index];
}
return false;
}
main()
{
int i=0,x;
while(cin>>x)
{
num[i]=x;
sum+=x;
i++;
}
n=i;
sort(num,num+n);
if(sum%4!=0) {cout<<"false"; return 0;}
sum=sum/4;
if(num[n-1]>sum) {cout<<"false"; return 0;}
if(f(0)) {cout<<"true"; return 0;}
else cout<<"false";
}
