目录
1、题目链接
2、题目
3、解法(回溯+剪枝)
4、代码
1、题目链接
78.子集(LeetCode)
2、题目
3、解法(回溯+剪枝)
思路:
枚举子集(答案)的第一个数选谁,第二个数选谁,第三个数选谁,依此类推。
dfs 中的 i 表示现在要枚举选 nums[i] 到 nums[n−1] 中的一个数,添加到 path 末尾。
如果选 nums[j] 添加到 path 末尾,那么下一个要添加到 path 末尾的数,就要在 nums[j+1] 到 nums[n−1] 中枚举了。
注意:不需要在回溯中判断 i=n 的边界情况,因为此时不会进入循环,if i == n: return 这句话写不写都一样。
4、代码
class Solution {
public:
vector<int> path; //存储当前路径
vector<vector<int>> ans;//结果集
void dfs( vector<int>& nums, int pos)//pos层数
{
ans.push_back(path);//增加结果集
for(int i = pos; i < nums.size();i++ )
{
path.push_back(nums[i]);
dfs(nums,i+1);//深搜
path.pop_back();//回溯
}
}
vector<vector<int>> subsets(vector<int>& nums) {
dfs(nums,0);
return ans;
}
};