全排列
题目:全排列
思路
通过深度优先搜索的方式,不断枚举每个数在当前位置的可能性,然后回溯到上一个状态,直到枚举完所有可能性得到正确的结果
res
:一个二维向量vector<vector<int>>
,用于存储所有生成的排列。path
:一个一维向量vector<int>
,用于存储当前正在构建的排列。check
:一个布尔数组bool check[7]
,用于标记数组nums
中的每个元素是否已经被用于当前排列中。这里假设nums
数组的大小不会超过6(因为数组索引从0开始,最大索引为6时,数组大小为7)。- 递归的终止条件是
path
的大小等于nums
的大小。 - 在递归过程中,使用
check
数组来确保不会重复使用同一个元素。 - 使用
path.push_back(nums[i])
和path.pop_back()
来实现回溯,即在尝试下一个元素之前,需要将当前元素从path
中移除,以便尝试其他可能的元素组合。 - 通过
check[i] = true
和check[i] = false
来标记元素是否已被使用。
C++代码
class Solution
{
vector<vector<int>> res;
vector<int> path;
bool check[7];
public:
void dfs(vector<int>& nums)
{
if(nums.size() == path.size())
{
res.push_back(path);
return ;
}
for(int i = 0; i < nums.size(); i ++ )
{
if(!check[i])
{
path.push_back(nums[i]);
check[i] = true;
dfs(nums);
// 回溯 -> 恢复现场
path.pop_back();
check[i] = false;
}
}
}
vector<vector<int>> permute(vector<int>& nums)
{
dfs(nums);
return res;
}
};
子集
题目:子集
思路1
我们先将所有结果个数为1的选出来,再再其基础上选出结果个数为2的,依次类推
- 从
pos
开始遍历nums
数组。对于每个位置i
,执行以下操作:
将nums[i]
添加到path
中。 - 递归调用
dfs
函数,以i + 1
作为新的起始位置,继续搜索。 - 在递归调用返回后,进行回溯操作:将刚刚添加到
path
中的nums[i]
移除,以便尝试其他可能的元素组合(或停止进一步搜索)。
C++代码
class Solution
{
vector<vector<int>> ret;
vector<int> path;
public:
vector<vector<int>> subsets(vector<int>& nums)
{
dfs(nums, 0);
return ret;
}
void dfs(vector<int>& nums, int pos)
{
ret.push_back(path);
for(int i = pos; i < nums.size(); i++)
{
path.push_back(nums[i]);
dfs(nums, i + 1);
path.pop_back();
}
}
};
思路2
依次枚举,1选不选,选的话在1基础上2选不选,选的话在2基础上选不选,枚举出所有结果;当当前位置等于数组大小时,将结果加入答案中
- 首先检查
pos
是否等于nums
的大小。如果是,说明已经遍历到数组的末尾,此时path
代表了一个完整的子集(可能是空集,也可能是包含数组所有元素的集合,这取决于dfs
的调用过程)。然后,将这个子集添加到ret
中,并返回 - 将
nums[pos]
添加到path
中,然后递归调用dfs
函数,以pos + 1
作为新的起始位置继续搜索。在递归调用返回后,执行回溯操作:从path
中移除nums[pos]
,以便尝试其他可能的元素组合或停止进一步搜索。
class Solution
{
vector<vector<int>> ret;
vector<int> path;
public:
vector<vector<int>> subsets(vector<int>& nums)
{
dfs(nums, 0);
return ret;
}
void dfs(vector<int>& nums, int pos)
{
if (pos == nums.size())
{
ret.push_back(path);
return;
}
path.push_back(nums[pos]);
dfs(nums, pos + 1);
path.pop_back();
dfs(nums, pos + 1);
}
};
找出所有子集的异或总和再求和
思路
本题和上题思路一样,我们使用上题的第一种思路,依次枚举,1选不选,选的话在1基础上2选不选,选的话在2基础上选不选;
不同的是将每个子集的值异或,并将其相加
- 从数组的第一个元素开始,递归地构建所有可能的子集
- 在每个递归步骤中,可以选择包含当前元素(通过异或操作更新
path
)或不包含当前元素(直接递归到下一个位置) int path
选择1
将其异或在path
上,再选2
异或在path
上;- 当到达数组的末尾时,将当前的
path
(即当前子集的异或和)加到res
上
C++代码
class Solution
{
int path;
int res;
public:
void dfs(vector<int>& nums, int pos)
{
res += path;
for(int i = pos; i < nums.size(); i ++ )
{
path ^= nums[i];
dfs(nums, i + 1);
path ^= nums[i];
}
}
int subsetXORSum(vector<int>& nums)
{
dfs(nums, 0);
return res;
}
};
全排列 II
题目:全排列 II
思路
同一个节点的分支中,相同的元素只能选择一次
同一个数只能使用一次
- 只关心不合法分支
if(cheak[i] == true) ||(i != 0 && nums[i] == nums[i-1] && cheak[i-1] == false))
C++代码
class Solution
{
vector<int> path;
vector<vector<int>> ret;
bool check[9];
public:
vector<vector<int>> permuteUnique(vector<int>& nums)
{
sort(nums.begin(), nums.end());
dfs(nums, 0);
return ret;
}
void dfs(vector<int>& nums, int pos)
{
if(pos == nums.size())
{
ret.push_back(path);
return;
}
for(int i = 0; i < nums.size(); i++)
{
if(check[i] == true|| (i != 0 && nums[i] == nums[i - 1] && check[i - 1] == false))
continue;
path.push_back(nums[i]);
check[i] = true;
dfs(nums, pos + 1);
path.pop_back();
check[i] = false;
}
}
};
- 只关心合法分支
if(cheak[i] == false) &&(i == 0 || nums[i] != nums[i-1] ||cheak[i-1] != false))
C++代码
class Solution
{
vector<int> path;
vector<vector<int>> ret;
bool check[9];
public:
vector<vector<int>> permuteUnique(vector<int>& nums)
{
sort(nums.begin(), nums.end());
dfs(nums, 0);
return ret;
}
void dfs(vector<int>& nums, int pos)
{
if(pos == nums.size())
{
ret.push_back(path);
return;
}
for(int i = 0; i < nums.size(); i++)
{
if(check[i] == false && (i == 0 || nums[i] != nums[i - 1] || check[i - 1] != false))
{
path.push_back(nums[i]);
check[i] = true;
dfs(nums, pos + 1);
path.pop_back();
check[i] = false;
}
}
}
};
电话号码的字母组合
题目:电话号码的字母组合
思路
利用一个全局的字符串数组来帮我映射数组和字母之间的关系
- 如果
pos
等于digits
的长度,说明已经处理完所有数字,将当前的path
(即一个完整的字母组合)添加到结果数组ret
中,并返回 - 否则,对于当前数字
digits[pos]
,遍历其对应的所有字母(通过str[digits[pos] - '0']
访问。对于每个字母,执行以下操作 -
- 将当前字母添加到
path
的末尾。
- 将当前字母添加到
-
- 递归调用
dfs
函数,处理下一个数字pos + 1
。
- 递归调用
-
- 在递归返回后,将刚刚添加的字母从
path
中移除,以便尝试当前数字对应的下一个字母。
- 在递归返回后,将刚刚添加的字母从
C++代码
class Solution
{
vector<string> ret;
string path;
string str[10]={"",
"", "abc", "def",
"ghi", "jkl", "mno",
"pqrs", "tuv", "wxyz"
};
public:
vector<string> letterCombinations(string digits)
{
if(digits.size() == 0) return ret;
dfs(digits, 0);
return ret;
}
void dfs(string& digits, int pos)
{
if(pos == digits.size())
{
ret.push_back(path);
return;
}
for(auto ch : str[digits[pos] - '0'])
{
path.push_back(ch);
dfs(digits, pos + 1);
path.pop_back();
}
}
};
本站资源均来自互联网,仅供研究学习,禁止违法使用和商用,产生法律纠纷本站概不负责!如果侵犯了您的权益请与我们联系!
转载请注明出处: 免费源码网-免费的源码资源网站 » 穷举vs暴搜vs深搜vs回溯vs剪枝(一)
发表评论 取消回复