题目:子集
思路
回溯法
代码
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void function(vector<int>& nums, int startindex)
{
// 为什么要到这里写? 后面调用递归之前就不对
result.push_back(path);
// 到头了
if(startindex == nums.size())
{
return;
}
int i;
int size;
size = nums.size();
for(i = startindex; i < size; i++)
{
path.push_back(nums[i]);
function(nums, i+1);
path.pop_back();
}
return;
}
vector<vector<int>> subsets(vector<int>& nums) {
result.clear();
path.clear();
function(nums, 0);
return result;
}
};
在回溯函数开头就记录path
结果;
错误示范
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void function(vector<int>& nums, int startindex)
{
// 为什么要到这里写? 后面调用递归之前就不对
// 到头了
if(startindex == nums.size())
{
return;
}
int i;
int size;
size = nums.size();
for(i = startindex; i < size; i++)
{
path.push_back(nums[i]);
result.push_back(path);
function(nums, i+1);
path.pop_back();
}
return;
}
vector<vector<int>> subsets(vector<int>& nums) {
result.clear();
path.clear();
function(nums, 0);
return result;
}
};
在后面调用递归之前写result.push_back(path);
就会漏掉空集,因为它进不去for循环;