Paste_Image.png
Paste_Image.png
===================== 解題思路 =====================
用 backtrack 的方式將每一個(gè)數(shù)字放進(jìn) subset 中, 然後存入 result 基本的套路為
- 放入下一筆資料
- recursive call (DFS 作法 記得每一次的 DFS 都要修改查找的起點(diǎn))
- 刪除剛放入的資料
===================== C++ code ====================
<pre><code>
class Solution {
public:
/**
* @param S: A set of numbers.
* @return: A list of lists. All valid subsets.
*/
void backtrack(vector<vector<int>> &res, vector<int> &sub, int start, vector<int> &nums)
{
res.push_back(sub);
for(int i = start; i < nums.size(); i++)
{
sub.push_back(nums[i]);
backtrack(res, sub, i + 1, nums);
sub.pop_back();
}
}
vector<vector<int> > subsets(vector<int> &nums) {
// write your code here
vector<vector<int>> res;
vector<int> sub;
backtrack(res, sub, 0, nums);
return res;
}
};
<code><pre>
