Subsets

Paste_Image.png Paste_Image.png

===================== 解題思路 =====================

用 backtrack 的方式將每一個數字放進 subset 中, 然後存入 result 基本的套路為

1. 放入下一筆資料
2. recursive call (DFS 作法 記得每一次的 DFS 都要修改查找的起點)
3. 刪除剛放入的資料

===================== 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>